POJ 2386 Lake Counting
简单的DFS,用了stack代替递归,输入有问题,搞了蛮久,算法是没问题。所以以后一定要记得加上检查输入的那一步
然后对于点的定义以后就这么办吧
此外还有stack的用法,也可以这样
//POJ 2386
#include <cstdio>
#include <stack>
using namespace std;
class Point
{
public:
Point(int xx, int yy)
{
x=xx;
y=yy;
}
int x, y;
};
int main()
{
int n, m, ans=0;
scanf("%d%d", &n, &m);
const int maxn = 200, maxm = 200;
char g[maxn][maxm];
for (int i=0;i<n;i++)
{
scanf("\n");
for (int j=0;j<m;j++)
scanf("%c", &g[i][j]);
}
stack<Point> s;
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
if (g[i][j]=='W')
{
g[i][j] = '.';
s.push(Point(i, j));
while (s.size())
{
Point p = s.top();
s.pop();
for (int dx=-1;dx<2;dx++)
{
for (int dy=-1;dy<2;dy++)
{
int nx = p.x+dx, ny = p.y+dy;
if (nx<0||ny<0||nx>=n||ny>=m) continue;
if (g[nx][ny]=='W')
{
g[nx][ny] = '.';
s.push(Point(nx, ny));
}
}
}
}
ans++;
}
printf("%d\n", ans);
return 0;
}