POJ 1562 Oil Deposits(DFS:求八连通分量个数)
http://poj.org/problem?id=1562
题意:输入是一个R行C列的字符网格,表示油田,问你这个网格中有多少个由油田构成的连通分量.其中上下左右对角线相邻的网格油都算一个连通分量.
分析:典型的DFS,我们只需要对于网格中的每个油格,做一次DFS即可.(且还需要该油格之前没有被走过).
AC代码:
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=100+5;
int R,C;
int cnt;//连通分量数目
char grid[maxn][maxn];
void dfs(int x,int y)
{
if(x<0 || x>=R || y<0 || y>=C || grid[x][y]!='@')
return ;
grid[x][y]='*';//这样做我就少用一个vis数组标记该点被走过
dfs(x+1,y);
dfs(x,y+1);
dfs(x-1,y);
dfs(x,y-1);
dfs(x+1,y+1);
dfs(x-1,y-1);
dfs(x+1,y-1);
dfs(x-1,y+1);
}
int main()
{
while(scanf("%d%d",&R,&C)==2&&R)
{
cnt=0;
for(int i=0;i<R;i++)
scanf("%s",grid[i]);
for(int i=0;i<R;i++)
for(int j=0;j<C;j++)
if(grid[i][j]=='@')
{
cnt++;
dfs(i,j);
}
printf("%d\n",cnt);
}
return 0;
}
分享到:
相关推荐
poj 2488——dfs深度优先遍历 //给行数列数,求问能否遍历,给出字典序的一种遍历
POJ3177-Redundant Paths 【Tarjan-边双连通分量-缩点】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/GPAY6Z 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ1020-Anniversary Cake 解题报告+AC代码
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
POJ3352-Road Construction 【Tarjan-边双连通分量-缩点】 解题报告+AC代码 http://hi.csdn.net/!s/0T8UO5 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ上的DP分类: 容易: 1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1208, 1276, 1322, 1414, 1456, 1458, 1609, 1644, 1664, 1690, 1699, 1740(博弈), 1742, 1887, 1926(马尔科夫矩阵,求...
初学者练题开始------在POJ上(注:是百练) 初学者练题开始------在POJ上(注:是百练) 初学者练题开始------在POJ上(注:是百练)
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ1691-Painting A Board 【拓扑+DFS】 解题报告+AC代码
北大POJ初级题-数据结构:解题报告+AC代码
POJ 1300 Door Man:无向图、欧拉定理、gets、sscanf
NULL 博文链接:https://128kj.iteye.com/blog/1754756
POJ2186-Popular Cows 【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
北大POJ3414-Pots 解题报告+AC代码
codefores/problemset/还有HDUOJ、POJ和洛谷/这几个文件夹的以后可能还会更新吧,因为无聊的时候可能会去刷刷题,当然其它的也有可能更新,以后的事也说不准。 update 20210123 开始转战。以后有时间偶尔可能会在...
poj 2820 古代密码 http://poj.grids.cn/problem?id=2820 可直接运行
POJ 3131 双向BFS解立体八数码问题
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...