[UVA][BFS] 11359 - Guards, Imbecile Guards
|
You have a square maze of size N x N. You begin from a source cell and start your journey in hope of reaching the target cell in minimum number of moves. You can move to new cell if it shares an edge with the current cell you are standing on. The minimum moves required aren’t always the Manhattan distance as there are few obstacles placed on certain places of the maze. You have to avoid those obstacles in your path. In addition to the obstacles, there are more impediments in the form of guards. The guards, however, aren’t that clever and they are also short-sighted. Initially every guard monotonously walks to the right. If it encounters an obstacle or reaches the end of the maze (last column) it turns left and starts walking. It walks left until it reaches an obstacle or the end (first column) when it changes direction to the right and starts walking. Every guard moves 1 cell per unit time. Your speed is also 1 cell per unit time. In every unit time, you can either make a move or stay in the same position. Staying in the same position also counts as a move.
You are caught by a guard if both of you land on the same cell at the same time or if you bump into each other during a move. In the latter case, you are caught in between the cells.
Every cell of the maze will be represented by one of the following:
S – Starting Cell.
T – Target Cell.
# - An Obstacle
X – A Guard
. – An Empty Cell
There will be at most 3 guards in a maze and all of them will be situated in different rows.
An example of the movement of a guard for first 6 seconds of its locomotion:
...... ...... ...... ...... ...... ...... ......
...... ...... ...... ...... ...... ...... ......
.#.X.. .#..X. .#...X .#..X. .#.X.. .#X... .#.X..
...... ...... ...... ...... ...... ...... ......
0 1 2 3 4 5 6
Input
The input file starts with an integer T(T<50) that indicates the number of test cases. Each case starts with a positive integer N(N<10). The next N lines contain N characters each that fill up the maze. There will be exactly one S character and one T character. There will be no more than 3 X characters in the maze.
Output
For each input, output the case number followed by the minimum number of moves required. If it is impossible to reach the target, output -1 instead.
|
Sample Input |
Output for Sample Input |
|
2 4 S... #### .... X.#T 5 T.X.. ..#.. .#S#. ..... ..... |
Case 1: -1 Case 2: 7 |
ProblemSetter:
Sohel Hafiz
Special Thanks: Vinay Singh
題目描述：
首先給一張地圖，求 S 到 T 的最短路徑，中間會有水平移動的障礙物 'X'。
每一行最多只會有一個 'X'，也就是說同一行只會有一個 'X' 才不會 'X' 之間相撞。
整張地圖最多有 3 個 'X'。
所有 'X' 一開始皆往右邊行進，每隔一秒會持續動作，中間過程為彈性碰撞。
從 S 到 T 的過程中，可以選擇上下左右或者是不動，但不能接觸到障礙物，也不能與障礙物進行穿越。
題目解法：
將移動時間納入 BFS 搜索中，再根據循環節迴避掉不可能的走法。
特別要處理與障礙物進行交換位置的處理。
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
int N;
char g[20][20];
struct DataX {
int vx[3], vy[3], dir[3];
};
DataX cycle[1024];
int cycle_len;
int dist[10][10][1024];
void bfs() {
int sx = 0, sy = 0, cc, ncc;
int tx, ty;
int i, j, k;
for(i = 0; i < N; i++) {
for(j = 0; j < N; j++) {
if(g[i][j] == 'S')
sx = i, sy = j;
for(k = 0; k < cycle_len; k++)
dist[i][j][k] = 0;
}
}
queue<int> X, Y, C;
dist[sx][sy][0] = 1;
X.push(sx), Y.push(sy), C.push(0);
int dx[] = {0, 0, 1, -1, 0};
int dy[] = {1, -1, 0, 0, 0};
while(!X.empty()) {
sx = X.front(), sy = Y.front(), cc = C.front();
X.pop(), Y.pop(), C.pop();
ncc = (cc+1)%cycle_len;
for(i = 0; i < 5; i++) {
tx = sx + dx[i], ty = sy + dy[i];
if(tx < 0 || ty < 0 || tx >= N || ty >= N || g[tx][ty] == '#')
continue;
int ok = 1;
for(j = 0; j < 3 && ok; j++) {
if(tx == cycle[ncc].vx[j] && ty == cycle[ncc].vy[j])
ok = 0;
if(cycle[ncc].vx[j] == sx && cycle[ncc].vy[j] == sy &&
cycle[cc].vx[j] == tx && cycle[cc].vy[j] == ty)
ok = 0; // cross (cause bump into each other during a move)
}
if(ok) {
if(dist[tx][ty][ncc] == 0) {
dist[tx][ty][ncc] = dist[sx][sy][cc] + 1;
if(g[tx][ty] == 'T') {
printf("%d\n", dist[sx][sy][cc]);
return;
}
X.push(tx), Y.push(ty), C.push(ncc);
}
}
}
}
puts("-1");
}
int main() {
int testcase, cases = 0;
int i, j, k;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d", &N);
memset(cycle, -1, sizeof(cycle));
cycle_len = 1;
int m = 0;
for(i = 0; i < N; i++) {
scanf("%s", g[i]);
for(j = 0; j < N; j++) {
if(g[i][j] == 'X') {
if(j+1 >= N || g[i][j+1] == '#') {
if(j-1 < 0 || g[i][j-1] == '#') {
g[i][j] = '#';
continue;
}
}
cycle[0].vx[m] = i;
cycle[0].vy[m] = j;
cycle[0].dir[m] = 1; // next direction right.
if(j+1 >= N || g[i][j+1] == '#')
cycle[0].dir[m] = 0; // next direction left.
m++;
}
}
}
do {
int CC = cycle_len;
DataX &r = cycle[CC];
for(i = 0; i < m; i++) {
r.vx[i] = cycle[CC-1].vx[i];
r.vy[i] = cycle[CC-1].vy[i] + (cycle[CC-1].dir[i] ? 1 : -1);
r.dir[i] = cycle[CC-1].dir[i];
int nx = r.vx[i], ny = r.vy[i] + (r.dir[i] ? 1 : -1);
if(ny >= N || g[nx][ny] == '#' || ny < 0 || g[nx][ny] == '#')
r.dir[i] = !r.dir[i];
}
int same = 1;
for(i = 0; i < m; i++) {
same &= r.vx[i] == cycle[0].vx[i];
same &= r.vy[i] == cycle[0].vy[i];
same &= r.dir[i] == cycle[0].dir[i];
}
if(same) break;
cycle_len++;
} while(true);
printf("Case %d: ", ++cases);
bfs();
}
return 0;
}