Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
otal Submission(s): 227 Accepted Submission(s): 56
Problem Description
You are now in a maze. You mark all the blocks you've visited by '@',
so when you see a wall '#' or a visited block '@' in front of you, you
will make a right turn. Otherwise, that means you don't have a wall or a
visited block in front, you'll go forward. When you reach the door 'D', congratulations!
####
#Y@#
##D#
####
Look at the maze above, you are now in 'Y', facing left, and seeing a wall in
front of you. You turn right, a wall again; turn right again, visited block;
turn right once again, still a wall. After three continuous turnings, you realize
the rest time of your life will be making turnings.
Input
The first line is T(T<=20), then T cases follow.
Each case has two numbers n and m(4<=n,m <= 20), the boundary of the maze will
always be '#', in the maze, there will
be exactly one 'Y', one 'D'. Normal blocks are marked with '.'.
At first you are facing left.
Output
"YES" if you can go out of the maze(reach 'D'). "NO" otherwise.
Sample Input
2
4 4
####
#.Y#
##D#
####
4 4
####
#.Y#
#D##
####
Sample Output
NO
YES
#include < iostream > #include < stdio.h > using namespace std; char a[ 21 ][ 21 ]; int aa[][ 4 ] = {{ 0 , 1 , 2 , 3 },{ 1 , 2 , 3 , 0 },{ 2 , 3 , 0 , 1 },{ 3 , 0 , 1 , 2 }}; int kk = 0 ,flag = 0 ; int x_end,y_end; void dfs( int x, int y){ int k = kk; if (x == x_end && y == y_end) // 不能用=='D' 因为在上一层已经将 D的值改变 { flag = 1 ; return ; } for ( int i = 0 ;i < 4 &&! flag; ++ i) { if (aa[k][i] == 0 && a[x][y - 1 ] != ' # ' ) { a[x][y - 1 ] = ' # ' ; kk = 0 ;dfs(x,y - 1 ); break ; // 不能回溯的 因为只有一条路可走 } if (aa[k][i] == 1 && a[x - 1 ][y] != ' # ' ) { a[x - 1 ][y] = ' # ' ;kk = 1 ;dfs(x - 1 ,y); break ; } if (aa[k][i] == 2 && a[x][y + 1 ] != ' # ' ) { a[x][y + 1 ] = ' # ' ;kk = 2 ;dfs(x,y + 1 ); break ; } if (aa[k][i] == 3 && a[x + 1 ][y] != ' # ' ) { a[x + 1 ][y] = ' # ' ;kk = 3 ;dfs(x + 1 ,y); break ; } }} int main() { // freopen("in.txt","r",stdin); int T; int n,m; 4 scanf( " %d " , & T); for ( int i = 1 ;i <= T;i ++ ) { kk = 0 ; flag = 0 ; // 在循环的开始对kk和flag进行清零 scanf( " %d%d " , & n, & m); getchar(); for ( int j = 1 ;j <= n;j ++ ) { for ( int k = 1 ;k <= m;k ++ ) { scanf( " %c " , & a[j][k]); if (a[j][k] == ' D ' ) { x_end = j; y_end = k; } } getchar(); } for ( int j = 1 ;j <= n;j ++ ) for ( int k = 1 ;k <= m;k ++ ) { if (a[j][k] == ' Y ' ) { a[j][k] = ' # ' ; dfs(j,k); } } if (flag == 1 ) printf( " YES\n " ); else printf( " NO\n " ); } return 0 ; }
转载于:https://www.cnblogs.com/cyiner/archive/2011/05/16/2048219.html
