2014-07-28

UVa 11705 - Grasshopper

1. Input
2. Output
3. Sample Input
4. Sample Output
5. Solution

We are at a funfair, where an array of trampolines, named ‘’The Grasshopper Labyrinth’’, catches our attention. As the figure below shows, all of them are labelled with non-negative integers:

\epsfbox{p11705a.eps}

People are inside, jumping from one trampoline to another, trying to reach the trampoline in the northwest corner, where the exit to the attraction is located. If you reach the exit fast enough, you may win a prize. However, in order to be eligible for the prize, you must abide by the following rule: after leaping from a trampoline labelled with z, you need to get to another one z trampolines away, in the same row or column.

Therefore, your problem is to find the shortest path from any trampoline to the way out, measured by the number of leaps needed. Since the length of the jump from any trampoline is given, it is sufficient to label each trampoline with the direction of the best jump from it.

\epsfbox{p11705b.eps}

For a given starting position, a path is considered shorter than another if it requires a smaller number of jumps; in case of a tie, the path whose first step gets you northmost in the array is to be preferred; and in case of a tie, the one getting you westmost.

Instead of these symbols, we are using the plain text ones: the appropriate cardinal point (‘N’, ‘S’, ‘E’ or ‘W’) for the arrows, ‘X’ for the trampolines without possible escape, and the asterisk ‘*’ for the special trampoline at the upper left position, which represents the exit.

Input

Several cases are given in a single test file. The first line in each test case contains a pair of integers between 1 and 50, separated by a single space; the first is the number of rows and the second the number of columns in the matrix. Then, the entries in the matrix follow, line by line, each element being a non-negative integer, again separated by single whitespace characters. A 0 x 0 matrix will denote the end of the test cases, and hence should not be analyzed.

Output

The expected output of each data case is a character matrix. Each element is one of the allowed charset, N'',S’’, E'',W’’, X'' or*’’, as described above. The output for each case is followed by a blank line.

Sample Input

3 4
0 2 2 5
3 1 1 2
2 2 2 1
1 20
0 3 3 3 2 5 10 5 3 4 5 4 4 4 6 4 10 3 5 1
5 6
0 7 2 4 4 4
3 1 3 2 3 1
2 1 4 3 4 3
4 4 2 3 3 3
5 4 4 3 4 5
0 0

Sample Output

*SWX
EENW
NENW
*EEWWWXWWWWWWWWWXWWW
*XWSWX
ESSWSW
NWXWWX
EEEWNW
XXNNNX

Solution

題目描述：

每一個位置的彈簧上會標記一個數字 w，表示可以跳躍至上下左右其中一個方向的 w 距離所在。
求每一個位置下一步的方向，來獲得最短路徑 (跳躍次數) 到最左上角。

題目解法：

題目忘了講到字典順序，如果有相同的情況，則選擇跳躍越左上角越好。

#include <stdio.h> 
#include <queue>
#include <algorithm>
using namespace std;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
const char ds[] = {'S', 'E', 'N', 'W'};
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int n, m, g[64][64];
    while(scanf("%d %d", &n, &m) == 2 && n+m) {
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                scanf("%d", &g[i][j]);
                
        char ret[64][64] = {};
        int visited[64][64] = {}, x, y, tx, ty, d;
        int vx[64][64], vy[64][64];
        queue<int> X, Y;
        X.push(0), Y.push(0);
        while(!X.empty()) {
            x = X.front(), X.pop();
            y = Y.front(), Y.pop();
            for(int i = 0; i < 4; i++) {
                tx = x + dx[i], ty = y + dy[i], d = 1;
                while(tx < n && ty < m && tx >= 0 && ty >= 0) {
                    if(g[tx][ty] == d) {
                        if(visited[tx][ty] == 0) {
                            visited[tx][ty] = visited[x][y] + 1;
                            ret[tx][ty] = ds[i];
                            vx[tx][ty] = x, vy[tx][ty] = y;
                            X.push(tx), Y.push(ty);
                        } else if(visited[tx][ty] == visited[x][y] + 1 
                        && make_pair(x, y) < make_pair(vx[tx][ty], vy[tx][ty])) {
                            ret[tx][ty] = ds[i];
                            vx[tx][ty] = x, vy[tx][ty] = y;
                        }
                    }
                    tx += dx[i], ty += dy[i], d++;
                }
            }
        }
        for(int i = 0; i < n; i++, puts("")) {
            for(int j = 0; j < m; j++) {
                if(i == 0 && j == 0)
                    putchar('*');
                else if(visited[i][j] == 0)
                    putchar('X');
                else
                    putchar(ret[i][j]);
            }
        }
        puts("");
    }
    return 0;
}

Morris' Blog