【紫书】Oil Deposits UVA - 572 dfs求联通块

题意:给你一个地图,求联通块的数量。

题解:

for(所有还未标记的‘@’点)

  边dfs边在vis数组标记id,直到不能继续dfs。

输出id及可;

ac代码:

#define _CRT_SECURE_NO_WARNINGS
#include "stdio.h"
#include<stdio.h>
#include<algorithm>
#include<string>
#include<vector>
#include<list>
#include<set>
#include<iostream>
#include<string.h>
#include<queue>
#include<string>
#include<sstream>
using namespace std;
const int maxn = +;
string map[maxn];
int ans;
int idx[maxn][maxn];
int n, m;
void dfs(int r,int c,int id) {
if (r<||c<||r>=n||c>=m||map[r][c] == '*'||idx[r][c])return;
idx[r][c] = id;
for(int dr=-;dr<=;dr++)
for (int dc = -; dc <= ; dc++)
if(dr||dc)dfs(r + dr, c + dc,id);
}
int main(){ while (cin >> n >> m) {
if (n == && m == )break;
ans = ;
memset(idx, , sizeof(idx));
for (int i = ; i < n; i++) {
cin >> map[i];
}
for (int i = ; i < n; i++)
for (int j = ; j < m; j++)
if (idx[i][j] == && map[i][j] == '@') dfs(i, j, ++ans);
cout << ans<<endl;
}
return ;
}
上一篇:使用Flexible实现手淘H5页面的终端适配(转)


下一篇:tomcat 启动异常 EOFException: Unexpected end of ZLIB input stream