计蒜客 踏青 dfs

题目:

https://www.jisuanke.com/course/2291/182234

思路:

紫书P163联通块问题。

1.遍历所有块,找到草地,判断合法性,合法其id值加一,最后加出来的id值就是联通块的数量。

2.注意结束条件,先判断是否结束dfs,再给vis赋值。

 #include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
//求联通块,紫书P163 int di[][]={{-,},{,},{,},{,-}};
int id;
int n,m,ex,ey,sx,sy;
char maze[][];
int vis[][]; bool judge(int x,int y)//判断合法性,合法:没有越界,没有被访问(vis==0),是草地(#)
{
if(x>=&&x<=n-&&y>=&&y<=m-&&vis[x][y]==&&maze[x][y]=='#')
return true;
return false;
} void dfs(int x,int y,int id)
{ // printf("x=%d y=%d id=%d\n",x,y,id);
if(!judge(x,y))
{
//printf("maze[%d][%d]=%c\n",x,y,maze[x][y]);
return;
}
vis[x][y]=id;
for(int i=;i<;i++)//四个方向
{
int nextx=x+di[i][];
int nexty=y+di[i][]; if(judge(nextx,nexty))
{
dfs(nextx,nexty,id);
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)==)
{
for(int i=;i<n;i++)
scanf("%s",maze[i]);
memset(vis,,sizeof(vis));
id=;
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
if(judge(i,j))
{
dfs(i,j,++id);
}
}
}
printf("%d\n",id);
// for(int i=0;i<n;i++)
// {
// for(int j=0;j<m;j++)
// {
// printf("%d ",vis[i][j]);
// }
// printf("\n");
// }
}
return ;
}
上一篇:[LeetCode] Two Sum


下一篇:标题栏新消息提示效果