提高课中的搜索一章讲过的Flood Fill算法。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
const int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0}, dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int n, m;
char g[N][N];
bool st[N][N];
void dfs(int sx, int sy)
{
st[sx][sy] = true;
for (int i = 0; i < 8; ++i)
{
int x = sx + dx[i], y = sy + dy[i];
if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '@' && !st[x][y])
dfs(x, y);
}
}
int main()
{
while (scanf("%d%d", &n, &m) != EOF && n && m)
{
for (int i = 0; i < n; ++i)
scanf("%s", &g[i]);
memset(st, 0, sizeof st);
int res = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
if (!st[i][j] && g[i][j] == '@')
dfs(i, j), ++res;
printf("%d\n", res);
}
return 0;
}