C-連続して見る

 
      

        YES NO NO NO NO YES 
      
 
      
 
      
 
      

        这个非常好可以作为dfs的典型，他用到了dfs的简化版，杜觉了dfs的代码的问题，值得借鉴他的他的方法。 
      
 
      

        他直接进行判断dfs的进入条件，用到了传入一个数字来记录这个代码所走的方向，同时也用到了每次的标记进行与之前的标记进行比较，杜绝了进入许多路径导致在别的路径可以走这个点，但是却被一个不通的路径进行了标记，导致终断，他用到了vis[xx][yy]>vis[x][y]&&ans<2,来避免这种情况。 
      
 
      
 
       
 
        
 
         
#include
#include
using namespace std;
const int maxv=1010;
const int inf=0xfffff;
int n,m;
int sx,sy,ex,ey;
int g[maxv][maxv];
int vis[maxv][maxv];
bool flag;
int fang[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
void dfs(int x,int y,int ans,int f)
{
	if(x==ex&&y==ey)
	{
		flag=1;
	    return;
	}
	for(int i=0;i<4&&flag==0;i++)
	{
		int xx=x+fang[i][0],yy=y+fang[i][1];
		if(xx>=1&&xx<=n&&yy<=m&&yy>=1&&(g[xx][yy]==0||(xx==ex&&yy==ey)))
		{
			if(i==f||f==-1)
			{
				vis[xx][yy]=ans;
				dfs(xx,yy,ans,i);
				if(flag==1)
				return ;
			}
			else
			if(ans<2&&vis[xx][yy]>vis[x][y])
			{
				vis[xx][yy]=ans+1;
				dfs(xx,yy,ans+1,i);
				if(flag)return;
			}
		}
		
	}
}
int main()
{
     while(scanf("%d%d",&n,&m)!=EOF)
     {
     	if(n==0&&m==0)
     	break;
     	for(int i=1;i<=n;i++)
     	{
     		for(int j=1;j<=m;j++)
     		scanf("%d",&g[i][j]);
		 }
		 int p;
		 scanf("%d",&p);
		 while(p--)
		 {flag=0;
		 	scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
		 	if(g[sx][sy]!=g[ex][ey])
		 	printf("NO
");
		 	else
		 	if(g[sx][sy]==0)
		 	printf("NO
");
		 	else
		 	{
		 	    fill(&vis[0][0],&vis[maxv][0],inf);
		 	     vis[sx][sy]=0;
		 	     dfs(sx,sy,0,-1);
		 	     if(flag)
		 	     printf("YES
");
		 	     else
		 	     printf("NO
");
			 }
		 }
	 }
}