2492 - Minecraft Maze
Today XiaoMing is playing Minecraft, an interesting game in which you can build your own virtual world.
Suddenly he found one underground maze which may contain a lot of diamonds, a precious raw material in Minecraft.
The maze consists of three components, path, soil and brick.
XiaoMing has a digging shovel with him, which can be used to dig away the soil, but not brick. The game plays in turn. Each turn XiaoMing can either move one unit of path, or dig one unit of soil(and no move this turn). He can only move to a neighboring place in four directions(up, down, left, right).
Given the decription of the maze, in order to get these precious diamonds as soon as possible, can you find out the minimum turns XiaoMing has to take to get these diamonds?
Input
The input consists of several test cases.
The first line of each test case contains two integers M and N (2 <= M, N <= 300).
Each of the following M lines contains N uppercase letters, each of which is one of 'X' (XiaoMing), 'D' (diamonds), 'B' (Brick), 'S' (soil) and 'P' (path). Both 'X' and 'D' appear only once.
Output
For each test case, please output the minimum turns XiaoMing has to take in a separate line. If XiaoMing can't arrive at the diamonds, output "-1" instead.
Examples
Input
3 4 XSPS PPBP BBDP 0 0
Output
8
Solution C++
#include <cstdio> #include <cstring> #include <queue> using namespace std; int m, n; struct node{ int x, y; node(int a, int b){ x = a; y = b; } }*xm, *d; char maze[301][301]; int dist[301][301], steps; bool vis[301][301]; queue<node*> q; void PUSH(int a, int b){ if(vis[a][b] || a < 1 || b < 1 || a > m || b > n || maze[a][b] == 'S') return; q.push(new node(a, b)); dist[a][b] = steps+1; vis[a][b] = 1; } int bfs(){ memset(vis, 0, sizeof(vis)); memset(dist, 0, sizeof(dist)); node *cur = new node(xm->x, xm->y); while(!q.empty()) q.pop(); q.push(cur); vis[xm->x][xm->y] = 1; while(!q.empty()){ cur = q.front(); q.pop(); steps = dist[cur->x][cur->y]; if(cur->x == d->x && cur->y == d->y) return dist[d->x][d->y]; if(maze[cur->x][cur->y] == 'L'){ maze[cur->x][cur->y] = 'P'; vis[cur->x][cur->y] = 0; PUSH(cur->x, cur->y); }else{ PUSH(cur->x - 1, cur->y); PUSH(cur->x, cur->y - 1); PUSH(cur->x, cur->y + 1); PUSH(cur->x + 1, cur->y); } } return -1; } int main(){ int i, j; while(scanf("%d%d", &m, &n) && m||n){ for(i = 1; i <= m; i++) for(j = 1; j <= n; j++){ scanf(" %c ", &maze[i][j]); if(maze[i][j] == 'X') xm = new node(i, j); else if(maze[i][j] == 'D') d = new node(i, j); } printf("%d\n", bfs()); } return 0; }