Question

杭电acm网站1010 一道搜索题 求个能ac的代码！谢谢大牛们！

Answer 1

注意剪枝 已AC过的 求采纳！>_<
#include <cstdlib>
#include <iostream>
#include <math.h>

using namespace std;

char c[10][10];
int n,m,t;
int wall;
int si,sj,di,dj;
int flag;
int step[4][2]={{0,-1},{-1,0},{0,1},{1,0}};

void dfs(int i,int j,int sec)
{
if(i==di && j==dj && sec==t)
{
flag=1;
return ;
}
if(abs(di-i)+abs(dj-j)>t-sec || (t-sec-abs(di-i)-abs(dj-j))%2!=0)
{
flag=0;
return ;
}
for(int k=0;k<4;k++)
{
if(i+step[k][0]<0 || i+step[k][0]>=n || j+step[k][1]<0 || j+step[k][1]>=m)
continue;
if(c[i+step[k][0]][j+step[k][1]]!='X')
{
c[i+step[k][0]][j+step[k][1]]='X';
dfs(i+step[k][0],j+step[k][1],sec+1);
c[i+step[k][0]][j+step[k][1]]='.';
}
if(flag)
return ;
}
}

int main(int argc, char *argv[])
{
while(cin>>n>>m>>t)
{
if(n==0 && m==0 && t==0)
break;
wall=0;
flag=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>c[i][j];
if(c[i][j]=='S')
{
si=i;
sj=j;
c[i][j]='X';
}
else if(c[i][j]=='D')
{
di=i;
dj=j;
c[i][j]='.';
}
else if(c[i][j]=='X')
{
wall++;
}
}
}
if(n*m-wall>=t)
{
dfs(si,sj,0);
}
if(flag)
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
}
system("PAUSE");
return EXIT_SUCCESS;
}