zoj 2100 Seeding

zoj 2100 Seeding

/*
深搜+回溯
令人崩溃的回溯啊。。。
用了2hours分析递归过程。。。
”拖拉机“不会分身
只有一条路径走到头把所有可耕种的点走完才算是YES
一开始理解错了
详见注释。。。
*/
#define LOCAL
#include<cstring>
#include<string>
#include<iostream>
using namespace std;
int dir[4][2]={0,1,0,-1,1,0,-1,0};//控制转向
int m,n,map[7][7],yes;
bool legal(int x,int y)//判断结点是否可访问
{if(x>=1&&x<=m&&y>=1&&y<=n)return true;return false;}
void DFS(int sum,int x,int y)
{
	if(yes) return;
	if(sum==m*n) {yes=1;return;}//除了石头所有都已经访问
	int sx,sy,i;
	for(i=0;i<4;i++)//转向
	{
		sx=x+dir[i][0];sy=y+dir[i][1];
		if(legal(sx,sy)&&!(map[sx][sy]))//若果该节点可访问
		{
			map[sx][sy]=1;//标记已经访问
			DFS(sum+1,sx,sy);//从当前节点向下一结点进发
			if(yes) return;
			if(map[sx][sy]==1)//注意这个条件,防止回溯时把记录石头的结点覆盖掉
				map[sx][sy]=0;
		}
	}
}
int main()
{
#ifdef LOCAL
       freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout);
#endif
 
	   int i,j,nstone;char ch;
	   while(cin>>m>>n&&m&&n)
	   {
		   memset(map,0,sizeof(map));
		   nstone=0;
		   for(i=1;i<=m;i++)
			{
				for(j=1;j<=n;j++)
				{
					cin>>ch;
					if(ch=='S'){map[i][j]=2;nstone++;}
			    }
			}
		   yes=0;map[1][1]=1;//标记出发点已经被访问
			DFS(nstone+1,1,1);//用nstone+1是因为出发点已经被访问
			if(yes){cout<<"YES"<<endl;}
			else{cout<<"NO"<<endl;}
	   }
		return 0;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注