很简单的深搜的一道题,由于这道题要找环的个数,并且认为相连当一个点的8个方向种中有一个方向和这个点相连。
这个题做法无非就是暴力每个点,然后满足条件的深搜即可。
感觉我自己的代码写的很无趣,大佬的代码都是没用vis数组判断,满足条件#的直接变成。即可
#include<bits/stdc++.h>
using namespace std;
char mmp[][];
int n,m,ans=;
int to[][]= {{,},{,-},{,},{-,},{,},{-,-},{,-},{-,}};
bool judge(int x,int y)
{
if(x<||y<||x>=n||y>=m||mmp[x][y]=='.')
return ;
return ;
}
void dfs(int x,int y)
{
mmp[x][y]='.';
for(int i=; i<; i++)
{
int tx=x+to[i][];
int ty=y+to[i][];
if(judge(tx,ty))
dfs(tx,ty);
}
}
int main()
{
cin>>n>>m;
for(int i=; i<n; i++)
for(int j=; j<m; j++)
cin>>mmp[i][j];
for(int i=; i<n; i++)
for(int j=; j<m; j++)
if(mmp[i][j]=='#')
{
dfs(i,j);
ans++;
}
cout<<ans<<endl;
return ;
}