2014-07-06

UVa 11200 - Sapitaur's labyrinth

1. Background
2. The Input
3. The Output
4. Sample Input
5. Sample Output
6. Solution

Background

In the distant planet Omicron Persei 8, there is a huge ocean of rotten dark water. In the middle of the ocean, there is the island of Nevreturn, where the damned Omicronian prisoners are sent. And on the island, there is an intricate labyrinth; only those prisoners who are able to escape from the labyrinth are given the merciful death. The labyrinth is surrounded by a deep abysm, where the mythical Sapitaur –half frog, half bull– lives, eating all those Omicronians who took a wrong course in the labyrinth.

You are an unfortunate Omicronian prisoner. Will you be able to escape from the labyrinth?
The Problem

Sapitaur’s Labyrinth consists of a matrix of cells. There are two kinds of cells, as shown in the figure below:

NOWSE. There is a wall extending from the North-West of the cell to the South-East.
NESOW. There is a wall extending from the North-East of the cell to the South-West.

Left: the two kinds of cells. Middle: a sample labyrinth with 3x3 cells, and 2 paths to escape. Right: a labyrinth with 15x10 cells, and only 1 path to escape (in red).

As you can see in the figure above, the entrance to the labyrinth is in the north (the upper row of the matrix), the exit is in the south (the lower row of the matrix), and the abysm extends along both sides of the labyrinth (beyond the first and last column of the matrix).

You have to count how many different paths exist to go from the entrance to the exit of the labyrinth. Obviously, these paths cannot go through the abysm.

The Input

The first line of the input contains an integer M, indicating the number of test cases.

For each test case, the first line contains two integers N M, between 1 and 500, where N is the width of the labyrinth (number of columns) and M is the height (number of rows). M lines follow; each line has N characters: “\” for NOWSE cells; and “/“ for NESOW cells.

The Output

For each test case, the output should consist of an integer indicating the number of different paths from the entrance to the exit of the labyrinth.

Sample Input

2
3 3
///
\\\
///
15 10
////\\\////\\//
/\\\\\/\/\/\\/\
\\\//\\\/\////\
//\\\/\///\//\\
\/\//\\/\\\\/\\
////////\\///\/
\\\\\\//\\\\\/\
\\/\//////\\///
\/\\/////\/\/\/
\///\///\\\\//\

Sample Output

1
2

2
1

Solution

題目描述：

給定用 \、/ 構成的迷宮，找到從上方進入且可以抵達下方的路徑總數。

題目解法：

這題目看似非常難，由於在建表處理上非常不方便。

但是仔細想想，考慮當前所在的格子類型，再考慮進來的方向，就能推出下一步會到達的格子。
(類似於鏡子反射的現象)

路徑總數不會太多，直接使用 DFS 進行搜索枚舉即可。

#include <stdio.h> 
#include <string.h>
char g[512][512];
int ret = 0, n, m;
const int dx[] = {1, 0, -1, 0}; // N, E, S, W
const int dy[] = {0, 1, 0, -1};
void dfs(int x, int y, int fdir) {
    if(x == n)	ret++;
    if(x < 0 || y < 0 || x >= n || y >= m)
        return;
    int dir = 0;
    if(g[x][y] == '\\') {
        switch(fdir) {
            case 0: dir = 1; break;
            case 1: dir = 0; break;
            case 2: dir = 3; break;
            case 3: dir = 2; break;
        }
    } else {
        switch(fdir) {
            case 0: dir = 3; break;
            case 3: dir = 0; break;
            case 1: dir = 2; break;
            case 2: dir = 1; break;
        }
    }
    dfs(x + dx[dir], y + dy[dir], dir);
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &m, &n);
        for(int i = 0; i < n; i++)
            scanf("%s", g[i]);
            
        ret = 0;
        for(int i = 0; i < m; i++)
            dfs(0, i, 0);
        printf("%d\n", ret);
    }
    return 0;
}

Morris' Blog