HD1010 Tempter of the Bone(一)

以前看杭电课件的时候，似懂非懂的把课件上的代码打了一遍，就交上去了，然后搁置起来，不了了之，昨天飘谊童鞋在纠结这个题，就想也尝试自己写一遍，不写不知道，一写下一跳，神马也不会，Orz……

思路：深搜+剪枝（多重剪枝）
我的AC代码:

[cpp]
#include
#include
#include
#include
#include
#include
using namespace std;
char map[9][9],step;
bool escape;
int e_x,e_y,s,t,dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};

void DFS(int x,int y,int step1)
{
if(x<=0||y<=0||x>s||y>t) //出界
return ;
if( escape == 1 ) //已搜到,退出
return ;
int temp=(step-step1)-abs(x-e_x)-abs(y-e_y); //奇偶性剪枝 && 最优性剪枝
if(temp<0||temp&1)
return;
if(x==e_x && y==e_y) //搜到终点
{
if(step1==step)
escape=1;
return ;
}
for(int i=0;i<4;i++){
if( map[x+dir[i][0]][y+dir[i][1]] != 'X' ) //深搜
{
map[x+dir[i][0]][y+dir[i][1]]= 'X';
DFS(x+dir[i][0],y+dir[i][1],step1+1);
map[x+dir[i][0]][y+dir[i][1]]='.';
}
}
return ;
}
int main(){
int i,j,s_x,s_y;
while(~scanf("%d%d%d",&s,&t,&step),s+t+step)
{
memset(map,0,sizeof(map));
for(i=1;i<=s;i++)
{
getchar();
for(j=1;j<=t;j++)
{
scanf("%c",&map[i][j]);
if(map[i][j]=='S')
{ s_x=i; s_y=j; }
if(map[i][j]=='D')
{ e_x=i; e_y=j; }
}
}
getchar(); //这个字符问题如果最后没有吸收,会判错,不知道杭电是怎样判题的
escape=0;
map[s_x][s_y]='X'; //一定要标记,否则会搜回来
DFS(s_x,s_y,0 );
if(escape)
puts("YES");
else
puts("NO");
}
return 0;
}

课件提供代码:

[cpp]
#include
# include
# include
# include
using namespace std;
char map[9][9];
int n,m,t,di,dj;
bool escape;
int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};
void dfs(int si,int sj,int cnt)
{
int i,temp;
if(si>n||sj>m||si<=0||sj<=0) return;
if(cnt==t&&si==di&&sj==dj) escape=1;
if(escape) return;
temp=(t-cnt)-abs(si-di)-abs(sj-dj);
if(temp<0||temp&1) return;
for(i=0;i<4;i++){
if(map[si+dir[i][0]][sj+dir[i][1]]!='X')
{
map[si+dir[i][0]][sj+dir[i][1]]='X';
dfs(si+dir[i][0],sj+dir[i][1],cnt+1);
map[si+dir[i][0]][sj+dir[i][1]]='.';
}
}
return;
}
int main()
{
freopen("Input.txt","r",stdin);
freopen("Output.txt","w",stdout);
int i,j,si,sj;
while(cin>>n>>m>>t)
{
if(n==0&&m==0&&t==0) break;
int wall=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
cin>>map[i][j];
if(map[i][j]=='S') { si=i; sj=j; }
else if(map[i][j]=='D') { di=i; dj=j; }
else if(map[i][j]=='X') wall++;
}
if(n*m-wall<=t)
{
cout<<"NO"< continue;
}
escape=0;
map[si][sj]='X';
dfs(si,sj,0);
if(escape) cout<<"YES"< else cout<<"NO"< }
return 0;
}

测试数据生成器:
[cpp]
#include
#include
#include
int main()
{
freopen("Input.txt","w",stdout);
int n=110;
srand(time(NULL));
while(n--)
{
int x,y,z,i,j,temp;
x=rand()%6+2;
y=rand()%6+2;
z=rand()%(x*y)+1;
printf("%d %d %d\n",x,y,z);
for(i=1;i<=x;i++)
{
for(j=1;j<=y;j++)
{
if(i==x&&j==y)
printf("S");
else if(i==x/2&&j==y/2)