POJ2386 Lake Counting 题解

来自markdown萌新的吐槽:原来目录不是必要的……?

原题

http://poj.org/problem?id=2386

题目大意

以前做过一道题叫细胞问题，和这题差不多，都是给一幅图，然后让你数图中有多少个集合。

题目分析

数据不大，暴搜暴搜，dfs和bfs都可以，这里用的是更容易写的dfs。

代码

#include<cstdio>
bool map[110][110];
int n,m;
void work(int x,int y)
{if (x < 0 || y < 0 || x >= n || y >= m) return;if (!map[x][y]) return;map[x][y] = false;//当时写了truework(x - 1,y - 1);work(x - 1,y);work(x - 1,y + 1);work(x,y - 1);work(x,y + 1);work(x + 1,y - 1);work(x + 1,y);work(x + 1,y + 1);
}int main()
{int ans = 0;scanf("%d%d",&n,&m);getchar();for (int i = 0;i < n;i++){char t;for (int j = 0;j < m;j++){t = getchar();if (t == 'W') map[i][j] = true;else map[i][j] = false;}getchar();}for (int i = 0;i < n;i++)for (int j = 0;j < m;j++)if (map[i][j]) ans++,work(i,j);printf("%d",ans);return 0;
}

反思

太久没码程序人都变菜了……想当年打这样的dfs可是闭着眼睛打的【雾，注释这里一开始打了true是因为我把map和been数组弄混了，但其实这里只需要一个数组就够了，判重和记录都能在一个矩阵上做。