HD1010 Tempter of the Bone

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

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

[cpp] 
#include<stack> 
#include<cmath> 
#include<cstdio> 
#include<cstring> 
#include<cstdlib> 
#include<iostream> 
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<stdio.h> 
# include <iostream> 
# include <string.h> 
# include <stdlib.h> 
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"<<endl; 
           continue; 
       } 
       escape=0; 
       map[si][sj]='X'; 
       dfs(si,sj,0); 
       if(escape) cout<<"YES"<<endl; 
       else cout<<"NO"<<endl; 
   } 
   return 0; 
} 

测试数据生成器:
[cpp] 
#include<stdio.h> 
#include<stdlib.h> 
#include<time.h> 
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) 
                printf("D"); 
            else 
            { 
                switch(rand()%6) 
                { 
                case 0:case 1:case 2:case 3:case 4:printf(".");break; 
                case 5:printf("X"); 
                } 
            } 
        } 
        printf("/n"); 
    } 
    } 
    return 0; 
} 

对拍程序:
[cpp] 
#include<stdio.h> 
#include<string.h> 
int main() 
{ 
    char a[120][5],b[120][5]; 
    int i=0,j=0; 
    freopen("Output.txt","r",stdin); 
    while(~scanf("%s",a[i]))i++; 
    freopen("Output1.txt","r",stdin); 
    while(~scanf("%s",b[j]))j++; 
    for(i=0;i<j;i++) 
        if(strcmp(a[i],b[i])!=0) 
            printf("%d/n",i); 
    return 0; 
} 
作者：ice2013