DongGua: Save our SWJTU!
Time Limit:2000MS Memory Limit:65536K
Total Submit:46
Accepted:22
Description
One night ,Desgard_Duan was caught by an
alien named “DG”when he was sleeping soundly.
“Now,you are in a extremely
complicated maze, if you can’t escape from this maze,you will be trapped in it
all your life!And I will destroy SWJTU OJ! hhhhhhhhhhhhhhh”
“Why you choose
me?!”
“OK,shut up,now I will give you some prompts.This is a N rows and M
columns maze ,and then your start point (X1,Y1),the end of maze (X2,Y2).For
every location,i will give you a value which means the value of walls around
it.”
“What’s the value mean?”(mad)
“Xiao Xiao Duan Donggua,so clever ya!
If the location has a wall above it the variable has 8 added to it.
If
the location has a wall to the left of it the variable has 4 added to it.
If
the location has a wall below it the variable has 2 added to it.
If the
location has a wall to the right of it the variable has 1 added to it.”
But,as you know ,Duan Donggua’s ID is not so reliable.Can you help
him?
Input
For each case, the first line of input
contains two numbers: m and n (0 <= m, n <= 600).
The second line
contains two number X1, Y1. They are start point.
As the second line, two
number X2, Y2 are the end of maze. (0 <= X1, X2 < m, 0 <= Y1, Y2 <
n)
The following m lines include n numbers each. And this is the Matrix to
describe the maze.
Output
Your program should output a text file
with two lines:
The first line should be the number of moves required to get
from the start location to the end location.
The second line should be a
list of moves that will trace a path from the start position to the end position
without going through any walls. Each move is represented by a single letter U,
D, L or R for Up, Down, Left or Right respectively.
Sample Input
5 4
2 2
4 0
14 9 12 9
14 2 3 5
13 12 8 3
5 5 6 9
6 2 11 7
Sample Output
4
LDDL
Hint
Source
水题，记录开始到终点移动每一步的方向
1 #include "iostream" 2 #include "string" 3 #include "memory.h" 4 #include "queue" 5 #include "algorithm" 6 #include "cstdio" 7 using namespace std; 8 #define MAXN 1111 9 const char dir[] = {'U','D','L','R'}; 10 const int dx[] = {-1,1,0,0},dy[] = {0,0,-1,1}; 11 int map[MAXN][MAXN]; 12 int vis[MAXN][MAXN]; 13 string wall[MAXN][MAXN]; 14 int n,m; 15 int sx,sy,fx,fy; 16 17 struct node { 18 int x,y,time; 19 string path; 20 }now; 21 22 23 void gao(int temp,int i,int j) 24 { 25 wall[i][j] = ""; 26 if (temp - 8 >= 0) temp -= 8, wall[i][j] += 'U'; 27 if (temp - 4 >= 0) temp -= 4, wall[i][j] += 'L'; 28 if (temp - 2 >= 0) temp -= 2, wall[i][j] += 'D'; 29 if (temp - 1 >= 0) temp -= 1, wall[i][j] += 'R'; 30 } 31 32 bool judge(int x,int y) 33 { 34 if (x < 0 || y < 0 || x >= m || y >= n) return 1; 35 if (vis[x][y]) return 1; 36 return 0; 37 } 38 void bfs() 39 { 40 queue<node> q; 41 now.x = sx; 42 now.y = sy; 43 now.path =""; 44 now.time = 0; 45 vis[sx][sy] = 1; 46 q.push(now); 47 while (!q.empty()) 48 { 49 now = q.front(); 50 q.pop(); 51 if (now.x == fx && now.y == fy) 52 { 53 cout << now.time << endl; 54 cout << now.path <<endl; 55 return ; 56 } 57 int i; 58 node next; 59 for (i = 0;i < 4; ++ i) 60 { 61 if (wall[now.x][now.y].find(dir[i]) == -1) { 62 next.x = now.x + dx[i]; 63 next.y = now.y + dy[i]; 64 } else continue; 65 if (judge(next.x,next.y)) continue; 66 next.path = now.path + dir[i]; 67 next.time = now.time + 1; 68 vis[next.x][next.y] = 1; 69 q.push(next); 70 } 71 } 72 73 } 74 int main() 75 { 76 int i, j; 77 while ( cin >> m >> n ) { 78 memset(vis,0,sizeof(vis)); 79 scanf("%d%d%d%d",&sx,&sy,&fx,&fy); 80 for (i = 0;i < m; ++ i) 81 for (j = 0;j < n; ++ j) { 82 scanf("%d",&map[i][j]); 83 gao(map[i][j],i,j); 84 } 85 bfs(); 86 } 87 return 0; 88 }