解題區/解題區 - UVa

UVa 11700 - Pipes

contents

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

After writing a solver for the “moveable maze” game last week, you have grown tired of it. After all, you already know the optimal solution. To entertain yourself, you find another puzzle game called “Pipes”, and play that for a while. On one puzzle, you have not been able to find a solution by hand, and you think that there is no solution. You decide to write a program to tell you whether this is the case.

The game is played on a grid with R rows and C columns. Each square of the grid contains a black dot in the centre and black lines in the direction of some, none, or all of its north, east, south, and west neighbouring squares, with the following restriction: if two opposite directions both have lines, then at least one of the other two directions has a line as well. In other words, it is forbidden for a square to consist of a straight line.

The objective of the game is to rotate each square, as many times as you like, such that for each square, if it has a line going in a compass direction (that is, north, east, south, or west), then it has a neighbour in that compass direction and that neighbour has a line going in the opposite compass direction. In other words, each edge in the grid should either have a line on both sides or neither side.

Your task is to determine whether a given grid has a solution.

Input Specification

The input consists of several test cases.

The first line of each test case contains the two integers R and C, separated by spaces, with 1 <= R,C <= 12.

The following R lines of input each contain one row of the grid, from north to south. Each of these lines contains exactly C strings of letters, separated by spaces, that correspond to squares of the grid, from west to east. Their format is as follows:

  • If the string is the single character x, then the square does not contain a line to any of its neighbours.
  • Otherwise, the string contains some of the characters N, E, S, W, which indicate that a black line extends from this square’s centre in the direction of its north, east, south, or west neighbour, respectively. No character will appear in the string more than once.

Input is terminated by a line containing 0 0. These zeros are not a test case and should not be processed.

Sample Input

1
2
3
4
5
6
7
8
3 3
NW NW x
NES NESW W
E W x
2 2
ES x
x N
0 0

Output Specification

For each test case, output SOLVABLE if there is a solution to the puzzle, and UNSOLVABLE otherwise.
Output for Sample Input

1
2
SOLVABLE
UNSOLVABLE

Solution

題目描述：

一個類似水管通路的遊戲，每一格都會有四個方向的缺口，請將每一個缺口與相鄰的格子缺口對齊。

題目解法：

當初以為是要從某一個邊流向到另一個邊，但是題目並沒有說明這些，其實就假想每一個格子都會有四個方向的標記，翻轉每一個格子，標記和標記之間要對到。(有標記的邊一定要與另一個有標記的邊相鄰)

因此，類似於關燈遊戲的窮舉方式，從左上依序窮舉到右下，同時檢查上一列的條件是否符合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
int g[16][16][4], n, m;
int kind[16][16], solvable;
static const int dx[] = {-1, 0, 1, 0}; // N, E, S, W
static const int dy[] = {0, 1, 0, -1};
void rotate(int r, int c) {
    int t = g[r][c][0];
    for(int i = 1; i < 4; i++)
        g[r][c][i-1] = g[r][c][i];
    g[r][c][3] = t;
}
int check(int r, int c, int ign) {
    for(int i = 0; i < 4; i++) {
        if(i == ign)	continue;
        if(g[r][c][i]) {
            int tx = r + dx[i], ty = c + dy[i];
            if(tx < 0 || ty < 0 || tx >= n || ty >= m)
                return 0;
            if(!g[tx][ty][(i+2)%4])
                return 0;
        }
    }
    return 1;
}
void dfs(int r, int c) {
    if(solvable)
        return;
    if(c == m) {
        if(check(r, c-1, 2))
            dfs(r + 1, 0);
        return ;
    }
    if(r == n) {
        int f = 1;
        for(int i = 0; i < m; i++)
            f &= check(r-1, i, -1);
//		if(f)
//		for(int i = 0; i < n; i++) {
//			for(int j = 0; j < m; j++) {
//				printf("[%d, %d] ", i, j);
//				for(int k = 0; k < 4; k++)
//					printf(" %d", g[i][j][k]);
//				puts("");
//			}
//		}
        solvable |= f;
        return;
    }
    
    if(kind[r][c] == 0) {
        if(check(r-1, c, -1)) {
            if(c && !check(r, c-1, 2))
                return;
            dfs(r, c+1);
        }
    } else {
        for(int i = 0; i < kind[r][c]; i++, rotate(r, c)) {
            if(check(r-1, c, -1)) {
                if(c && !check(r, c-1, 2))
                    continue;
                dfs(r, c+1);
            }
        }
    }
}
int main() {
    char s[128], mapped[128] = {};
    mapped['N'] = 0;
    mapped['E'] = 1;
    mapped['S'] = 2;
    mapped['W'] = 3;
    while(scanf("%d %d", &n, &m) == 2 && n + m) {
        memset(g, 0, sizeof(g));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                scanf("%s", s);
                if(s[0] != 'x') {
                    for(int k = 0; s[k]; k++)
                        g[i][j][mapped[s[k]]] = 1;
                }
                if(s[0] == 'x')
                    kind[i][j] = 0;
                else {
                    int len = strlen(s);
                    if(len == 4)
                        kind[i][j] = 0;
                    else if(len == 1 || len == 3)
                        kind[i][j] = 4;
                    else {
                        if(g[i][j][0] == g[i][j][2])
                            kind[i][j] = 2;
                        else
                            kind[i][j] = 4;
                    }
                }
            }
        }
        solvable = 0;
        dfs(0, 0);
        puts(solvable ? "SOLVABLE" : "UNSOLVABLE");
    }
    return 0;
}