POJ 2386 Lake Counting（DFS）

本文主要是介绍POJ 2386 Lake Counting（DFS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

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

题解：

遍历一次，遇到w，一次DFS后，与此w连接的所有w都被替换成‘ . ’，直到遍历完图中不再存在w为止，总共进行DFS的次数就是答案了。

代码：

#include<stdio.h>
int N,M;
char map[110][110];
void dfs(int x,int y)
{map[x][y]='.';int i,j;int mx,my;for(i=-1;i<=1;i++){for(j=-1;j<=1;j++){mx=x+i;my=y+j;if(map[mx][my]=='W'&&mx>=0&&mx<N&&my>=0&&my<M)dfs(mx,my);}}return;
}
int main()
{while(~scanf("%d%d",&N,&M)){int i,j;for(i=0;i<N;i++){getchar();//注意消掉输入的回车for(j=0;j<M;j++){scanf("%c",&map[i][j]);}}int sum=0;for(i=0;i<N;i++){for(j=0;j<M;j++){if(map[i][j]=='W'){sum++;dfs(i,j);}}}printf("%d\n",sum);}return 0;
}

这篇关于POJ 2386 Lake Counting（DFS）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---