我的深搜学得太烂了,所以打算写一下题解。
using namespace std;
int n,m;
const int N=110;
int a[N][N];
bool st[N][N];//很巧妙
int dfs(int x,int y)
{
if(x<1||x>n||y>n||y<1||!a[x][y]||st[x][y])
{
return 0;
}
st[x][y]=1;//标记已经走过,不然会和之后的重复计算
//我一开始没想到这个方法,看了一下别人的代码,觉得这一步真的很巧妙
return dfs(x+1,y)+dfs(x,y+1)+dfs(x-1,y)+dfs(x,y-1)+a[x][y];
}
int main()
{
while(cin>>n>>m)
{
memset(a,0,sizeof a);
memset(st,0,sizeof st);
if(n==0&&m==0) break;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
}
}
int t=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(a[i][j]&&!st[i][j])//这一步也很关键
{
if(dfs(i,j)==m) t=1;
}
}
}
if(t) puts("YES");
else puts("NO");
}
return 0;
}