lzh

Tempter of the Bone Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 21915 Accepted Submission(s): 6011 Problem Description The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze. The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next second. He could not stay at one block for more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him. Input The 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. Output For 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 /*刚看到提示觉得就是一个普通的棋盘搜索的问题，因为以前做过所以马上开始敲代码，到后来发现连测试数据都过不了，再后来就是WA。后面记过调试才发现循环搜索遍历后没复原。后来终于自己的测试数据都过了，提交后才悲剧地发现TLE。看了很久之后觉得到网上找答案了，原来是一个剪枝没处理 。铜鼓这个题又又发现了很多问题 1.基本的算法要熟悉弄通，例如此题就是一个典型的DFS，我很久前学过但没怎么用，没很好的掌握。开始做时完全按照自己的思路，虽然写出来了但效率不高 2.算法效率越见重要，最后还是一个数学问题，多总结 */ //下面是自己盲目写的算法，虽然册数数据过了但超时 /*#include #include using namespace std; #define N 8 char maze[N][N]; bool flag[N][N]; int direction[4][2]={0,1,1,0,0,-1,-1,0}; bool sign; int num; void init() { int i,j; for(i=0;i=s) { if(maze[x][y]=='D') { sign=true; return ; } else continue; } else { if(maze[x][y]=='D') continue; else { cout<>row>>column>>limit) { getchar(); // if(!(row|column|limit)) //全0则输入结束 // break; if(0==row&&0==column&&0==limit) return 0; init(); for(i=1;i<=row;i++) { for(j=1;j<=column;j++) { cin>>maze[i][j]; if(maze[i][j]=='S') { Ss=i; Se=j; } if(maze[i][j]!='X') { flag[i][j]=true; num++; } } getchar(); } times=0; num=0; sign=false; flag[Ss][Se]=false; if(num-1>=limit) //限制的时间小于等于所有的街区数时才有可能有解 search(Ss,Se,limit,times); if(sign) cout<<"YES\n"; else cout<<"NO\n"; } return 0; } */ //之后经过剪枝后的代码 AC #include #include using namespace std; #define N 8 int ex,ey; //出口位置 int secs; //出口开启时间 bool sign; //找到出口的标志 bool flag[N][N]; //是否遍历过的标记数组 char maze[N][N]; int direction[4][2]={0,1,1,0,0,-1,-1,0}; void init() { int i,j; for(i=0;i>row>>column>>secs) { getchar(); //吸收回车 if(!(row|column|secs)) //全0则输入结束 break; init(); nums=0; sign=false; for(i=1;i<=row;i++) { for(j=1;j<=column;j++) { cin>>maze[i][j]; if(maze[i][j]=='S') { x0=i; y0=j; } else if(maze[i][j]=='D') { ex=i; ey=j; flag[i][j]=true; } else if(maze[i][j]=='X') nums++; else flag[i][j]=true; } getchar(); //吸收回车 } if(row*column-nums-1>=secs) dfs(x0,y0,0); if(sign) cout<<"YES\n"; else cout<<"NO\n"; } return 0; }