题目链接:http://poj.org/problem?id=1979
深度优先搜索非递归写法
#include <cstdio>
#include <stack>
using namespace std;
const int MAX_W = 25, MAX_H = 25;
char Map[MAX_W][MAX_H+1];
int W, H;
int DFS(int sx, int sy);
int main()
{
while (scanf("%d %d", &H, &W) == 2
&& W != 0 && H != 0) {
for (int i = 0; i < W; i++)
scanf("%s", Map[i]);
for (int i = 0; i < W; i++)
for (int j = 0; j < H; j++) {
if (Map[i][j] == '@')
printf("%d\n", DFS(i, j));
}
}
return 0;
}
int DFS(int sx, int sy)
{
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int Visited[MAX_W][MAX_H] = {0};
typedef pair<int, int> Position;
stack<Position> sta;
Visited[sx][sy] = 1;
int num = 1;
Map[sx][sy] = '.';
sta.push(Position(sx, sy));
while (!sta.empty()) {
Position p = sta.top(); sta.pop();
for (int i = 0; i < 4; i++) {
int nx = p.first + dx[i], ny = p.second + dy[i];
if (0 <= nx && nx < W && 0 <= ny && ny < H &&
Map[nx][ny] == '.' && !Visited[nx][ny]) {
sta.push(Position(nx, ny));
Visited[nx][ny] = 1;
num++;
}
}
}
return num;
}