主要在于判斷轉折了幾次。
以下是我的代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
using namespace std;
const int kMaxn = 1007;
const int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int n,m,map[kMaxn][kMaxn];
bool used[kMaxn][kMaxn];
int x1,y1,x2,y2;
bool dfs(int nowx,int nowy,int lastx,int lasty,int turn_times)
{
if(turn_times>2)
return false;
if(nowx==x2 && nowy==y2)
return true;
used[nowx][nowy]=true;
for(int i=0;i<4;i++)
{
int newx(nowx+dx[i]),newy(nowy+dy[i]);
if(newx<1 || newx>n || newy<1 || newy>m)
continue;
if(used[newx][newy])
continue;
if(map[newx][newy] && (newx!=x2 || newy!=y2))
continue;
if((lastx==nowx && nowx==newx) || (lasty==nowy && nowy==newy))
{
if(dfs(newx,newy,nowx,nowy,turn_times))
return true;
}
else
{
if(dfs(newx,newy,nowx,nowy,turn_times+1))
return true;
}
}
used[nowx][nowy]=false;
return false;
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
while(cin>>n>>m && (n || m))
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>map[i][j];
int question_num;
cin>>question_num;
while(question_num--)
{
cin>>x1>>y1>>x2>>y2;
if(!map[x1][y1] || !map[x2][y2] || map[x1][y1]!=map[x2][y2])
{
cout<<"NO"<<endl;
continue;
}
memset(used,false,kMaxn*kMaxn*sizeof(bool));
if(dfs(x1,y1,x1,y1,0))
cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
/*
cout<<static_cast<double>(clock())/CLOCKS_PER_SEC<<endl;
//*/
return 0;
}
posted on 2011-03-01 11:29
lee1r 閱讀(374)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：搜索