题解 | #数芝麻#

我的深搜学得太烂了，所以打算写一下题解。

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;
}