首页 > 代码库 > SWJTU 2184迷宫
SWJTU 2184迷宫
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 42 24 014 9 12 914 2 3 513 12 8 35 5 6 96 2 11 7
Sample Output
4LDDL
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 }
SWJTU 2184迷宫