Escaping from a maze

**Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 27185    Accepted Submission(s): 6630

**

\

Problem Description

Given an M by N maze with m rows and N columns, there are two positions in the maze. Gloria wants to go from one position in the maze to the other. Gloria can only walk to four adjacent positions, but gloria can’t go outside the maze during the walk. Unfortunately, Gloria has no sense of direction, so she can’t take too many turns while she’s walking or she’ll faint. We assume that the two positions given are both open Spaces. Initially, Gloria faces an undefined direction and can start in any of four directions without making a turn. Can Gloria move from one position to another?

 

 

Input

The first line is an integer T (1 ≤ T ≤ 100), representing the number of test data. The next line is t group of test data. In each group of test data, the first line is two integers M and n (1 ≤ m, n ≤ 100), representing the number of maze rows and columns respectively. Where the character ‘.’ indicates that the position is open space, and the character ‘*’ indicates that the position is obstacle. There are only these two characters in the input data. The last line of each group of test data contains 5 integers K, X1, Y1, X2, y2 (1 ≤ K ≤ 10, 1 ≤ X1, x2 ≤ n, 1 ≤ Y1, y2 ≤ m), where K represents the maximum number of turns gloria can make. (x1, y1), (x2, y2) represent two positions, where x1 and x2 correspond to columns and y1 and y2 to rows.

 

 

Output

Each group of test data corresponds to a row. If Gloria can move from one position to another, print “yes”, otherwise print “no”.

 

 

Sample Input

2

5 5

. 支那

*. * *.

.

.

*…

1, 1, 1, 1, 3

5 5

. 支那

*. * *.

.

.

*…

2, 1, 1, 1, 3

 

 

Sample Output

no

yes

 

 

Source

“Wangxin EMp Cup” Program Design Invitational competition of Hangzhou Dianzi University

Title links: acm.hdu.edu.cn/showproblem…

Analysis: DFS is invalid, I spent two and a half hours on this question in the second training match, debugging for a long time, too, as a result, the ranking dropped a lot of QAQ, I did the only question written by two people, and then the mentally retarded I did not write the check-in question, directly GG two questions, my teammates, I did not write the check-in question, I was just killing QAQ

In fact, this DFS is very classic, is a bit more conditions, judgment is a bit of trouble, the following code!

1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 inline int read() 5 { 6 int x=0,f=1; 7 char ch=getchar(); 8 while(ch<'0'||ch>'9') 9 { 10 if(ch=='-') 11 f=-1; 12 ch=getchar(); 13 } 14 while(ch>='0'&&ch<='9') 15 { 16 x=x*10+ch-'0'; 17 ch=getchar(); 18 } 19 return x*f; 20} 21 int _x[4]={-1,0,1,0}; 22 int _y [4] = {0, 0, 1}; 23 24 char str[105][105]; 25 int x1,y1,x2,y2,k,q=0; 26 int n,m; 27 int turn[105][105]; 28 inline void dfs(int x,int y,int dir) 29 { 30 int ii,i,j; 31 if(x==x2&&y==y2) 32 { 33 if(turn[x][y]<=k) 34 { 35 q=1; 36 } 37 return; 38 } 39 if(turn[x][y]>k) 40 return; 41 if(x! =x2&&y! =y2&&turn[x][y]==k) 42 return; 43 for(ii=0; ii<4; ii++) 44 { 45 i=x+_x[ii]; 46 j=y+_y[ii]; 47 if(i<0||j<0||i>=m||j>=n) 48 { 49 continue; 50 } 51 if(turn[i][j]<turn[x][y]||str[i][j]=='*') 52 continue; 53 if(dir! =-1&&ii! =dir&&turn[i][j]<turn[x][y]+1) 54 continue; 55 turn[i][j]=turn[x][y]; 56 if(dir! =-1&&ii! =dir) 57 turn[i][j]++; 58 dfs(i,j,ii); 59 if(q) 60 return; 61 } 62 } 63 int T; 64 int main() 65 { 66 while(scanf("%d",&T)! =EOF) 67 { 68 while(T--) 69 { 70 scanf("%d%d",&m,&n); 71 for(int i=0; i<m; i++) 72 { 73 scanf("%s",str[i]); 74 } 75 scanf("%d%d%d%d%d",&k,&y1,&x1,&y2,&x2); 76 y1--,x1--,y2--,x2--; 77 memset(turn,9999999,sizeof(turn)); 78 q=0; 79 turn[x1][y1]=0; 80 dfs(x1,y1,-1); 81 if(q) 82 printf("yes\n"); 83 else 84 printf("no\n"); 85 } 86 } 87 return 0; 88}Copy the code