InputThe input consists of multiple test cases. The first line of each test case contains three integers N, M, and T (1 < N, M < 7; 0 < T < 50), which denote the sizes of the maze and the time at which the door will open, respectively. The next N lines give the maze layout, with each line containing M characters. A character is one of the following:
‘X‘: a block of wall, which the doggie cannot enter;
‘S‘: the start point of the doggie;
‘D‘: the Door; or
‘.‘: an empty block.
The input is terminated with three 0‘s. This test case is not to be processed.
OutputFor each test case, print in one line "YES" if the doggie can survive, or "NO" otherwise.
Sample Input
4 4 5 S.X. ..X. ..XD .... 3 4 5 S.X. ..X. ...D 0 0 0
Sample Output
NO YES
学到了剪枝的一些知识。
AC代码
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #define N 10 5 6 using namespace std; 7 8 int n,m,t,end_i,end_j; 9 bool visited[N][N],flag,ans; 10 char mapp[N][N]; 11 12 int abs(int a,int b) 13 { 14 if(a<b) return b-a; 15 else return a-b; 16 } 17 18 void DFS(int i,int j,int c) 19 { 20 if(flag) return ; 21 if(c>t) return ; 22 if(i<0||i>=n||j<0||j>=m) {return ;} 23 if(mapp[i][j]==‘D‘&&c==t) {flag=ans=true; return ;} 24 int temp=abs(i-end_i)+abs(j-end_j); 25 temp=t-temp-c; 26 if(temp&1) return ;//奇偶剪枝 27 28 if(!visited[i-1][j]&&mapp[i-1][j]!=‘X‘) 29 { 30 visited[i-1][j]=true; 31 DFS(i-1,j,c+1); 32 visited[i-1][j]=false; 33 } 34 if(!visited[i+1][j]&&mapp[i+1][j]!=‘X‘) 35 { 36 visited[i+1][j]=true; 37 DFS(i+1,j,c+1); 38 visited[i+1][j]=false; 39 } 40 if(!visited[i][j-1]&&mapp[i][j-1]!=‘X‘) 41 { 42 visited[i][j-1]=true; 43 DFS(i,j-1,c+1); 44 visited[i][j-1]=false; 45 } 46 if(!visited[i][j+1]&&mapp[i][j+1]!=‘X‘) 47 { 48 visited[i][j+1]=true; 49 DFS(i,j+1,c+1); 50 visited[i][j+1]=false; 51 } 52 } 53 54 int main() 55 { 56 int i,j,x,y,k; 57 while(cin>>m>>n>>t&&(m||n||t)) 58 { 59 memset(visited,false,sizeof(visited)); 60 k=0; 61 for(i=0;i<n;i++) 62 { 63 for(j=0;j<m;j++) 64 { 65 cin>>mapp[i][j]; 66 if(mapp[i][j]==‘S‘) 67 { 68 x=i;y=j; 69 visited[i][j]=true; 70 } 71 if(mapp[i][j]==‘D‘) 72 { 73 end_i=i;end_j=j; 74 } 75 if(mapp[i][j]==‘X‘)k++; 76 } 77 } 78 ans=flag=false; 79 if(n*m-k-1>=t) DFS(x,y,0); 80 if(ans) cout<<"YES"<<endl; 81 else cout<<"NO"<<endl; 82 } 83 return 0; 84 }
B - Tempter of the Bone(DFS+剪枝)
原文：https://www.cnblogs.com/ruruozhenhao/p/8783344.html