[UVA][dfs] 614 - Mapping the Route
Mapping the Route
| Mapping the Route |
Finding a path through a maze is a popular problem for computers. In this problem, a maze will consist of a rectangular array of square cells, each of which may have walls on the north, south, east and/or west sides of the cell. One cell will be identified as the starting point, and another will be identified as the goal. Your task is to find the unique route from the starting point to the goal, label each cell in the path with its sequence in the path, identify the cells that were visited but that were not in the path, and display the maze.
The algorithm you use to find a path through the maze must be the one described below.
Imagine a robot is positioned in the starting cell.
The robot first attempts to go west from that
cell, then north, then east, then south, in sequence.
The robot can move in the selected direction
if
- (a)
- there is no wall preventing it from moving in that direction, and
- (b)
- it has not yet been in the next cell in that direction.
When the robot reaches the goal, its trip is over. If the robot reaches a cell at which no further progress is possible, it retreats to the previous cell it occupied and attempts to move in the next untried direction.
Consider the simple maze shown on the left
below. It is two cells high and three cells wide.
The starting cell is labeled `S' and the goal cell
is labeled `G'. When the robot starts, it would
first try to move west (left), but finds a wall.
It then tries to move north (up), and is again
blocked by a wall. A wall also prevents it from moving
east (right), so it finally tries to move
south (down), and succeeds. From the new cell
it will eventually move east. Here it repeats its
movement algorithm. Although no wall blocks its potential
westward movement, it has already
'visited' the cell in that direction, so it next
tries to move north, and is successful. Unfortunately,
after moving north, it finds no way to extend its path,
and so it retreats to the previously occupied
cell. Now it tries to move east, and is successful.
From that cell it will move north, and there it
finds the goal. The maze that would be displayed
on the output is shown on the right below.
Note that the starting cell is labeled `1', each
cell in the path to the goal (including the one
containing the goal) is labeled with its sequence
number, and each cell that was visited but is not
in the path is labeled with question marks.
+---+---+---+ +---+---+---+
| S | | G | | 1|???| 5|
+ + + + + + + +
| | | 2 3 4|
+---+---+---+ +---+---+---+
Input
View the maze as an array of cells, with the northernmost row being row 1, and the westernmost column being column 1. In the maze above, the starting cell is row 1, column 1, and the goal cell is row 1, column 3.
There will be one or more mazes to process in the input. For each maze there will first
appear six integers. The first two give the height (number of rows) and width (numer of
columns) of the maze (in cells). The next two give the position (row and column number) of the
starting cell, and the last two give the position of the goal. No maze will have more than 12 rows
or 12 columns, and there will always be a path from the starting point to the goal.
Following the first six integers there will
appear one integer for each cell, in row major
order. The value of each integer indicates
whether a cell has a wall on its eastern side (1) and
whether it has a wall on its southern side (2). For
example, a cell with no eastern or southern
wall has a value of 0. A cell with only a southern wall has
a value of 2. A cell with both an
eastern and a southern wall has a value of 3. The cells on the periphery of the maze
always have appropriate walls to prevent the robot from leaving the maze;
these are not specified in the input data.
The last maze in the input data will be followed by six zeroes.
Output
For each maze, display the maze as shown in the example above and the expected output below, appropriately labeled and prefixed by the maze number. The mazes are numbered sequentially starting with 1. Print two blank lines after each dataset.
Sample Input
2 3 1 1 1 3 1 1 0 0 0 0 4 3 3 2 4 3 0 3 0 0 2 0 0 3 0 0 1 0 0 0 0 0 0 0
Sample Output
Maze 1 +---+---+---+ | 1|???| 5| + + + + | 2 3 4| +---+---+---+ Maze 2 +---+---+---+ |??? ???|???| + +---+ + | 3 4 5| + +---+ + | 2 1| 6| + +---+ + | | 7| +---+---+---+
Miguel A. Revilla
1999-03-24
題目說明：
機器人依序往 WNES 的方向嘗試，然後走到的所有路中，依據 stack 的感覺，
除了當前在 stack 中的點外，其餘的"走過的"點都是 ???，
輸入說明：
給定行、列接著起點與終點的座標。
接著會有 n*m 個數字，分別代表這格的 右邊與下邊有沒有牆壁。
1->右邊, 2->下邊, 3->兩邊都有
一次 dfs 就可以了。
#include <stdio.h>
#include <string.h>
int g[20][20], dg[20][20];
int sx, sy, ex, ey, n, m;
int check(int x, int y, int v) {
if(x <= 0 || x > n || y <= 0 || y > m)
return 0;
if(dg[x][y]&v)
return 0;
return 1;
}
int dfs(int x, int y, int dep) {
if(x == ex && y == ey) {
g[x][y] = dep;
return 1;
}
if(x <= 0 || x > n || y <= 0 || y > m)
return 0;
if(g[x][y])
return 0;
g[x][y] = dep;
int f = 0;
if(check(x, y-1, 1))
f = dfs(x, y-1, dep+1); // W
if(f) return 1;
if(check(x-1, y, 2))
f = dfs(x-1, y, dep+1); // N
if(f) return 1;
if(check(x, y, 1))
f = dfs(x, y+1, dep+1); // E
if(f) return 1;
if(check(x, y, 2))
f = dfs(x+1, y, dep+1); // S
if(f) return 1;
g[x][y] = -1;
if(x == sx && y == sy)
g[x][y] = 1;
return 0;
}
int main() {
int cases = 0;
int i, j;
while(scanf("%d %d", &n, &m) == 2) {
if(n == 0 && m == 0)
break;
scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
memset(g, 0, sizeof(g));
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
scanf("%d", &dg[i][j]);
dfs(sx, sy, 1);
printf("Maze %d\n\n", ++cases);
for(i = 1, putchar('+'); i <= m; i++)
printf("---+");
puts("");
for(i = 1; i <= n; i++) {
putchar('|');
for(j = 1; j <= m; j++) {
if(g[i][j] < 0)
printf("???");
else if(g[i][j] == 0)
printf(" ");
else
printf("%3d", g[i][j]);
if(j == m || (dg[i][j]&1))
putchar('|');
else
putchar(' ');
}
puts("");
for(j = 1, putchar('+'); j <= m; j++) {
if(i == n || (dg[i][j]&2))
printf("---+");
else
printf(" +");
}
puts("");
}
puts("\n");
}
return 0;
}