解題區/解題區 - UVa

UVa 11585 - Nurikabe

contents

  1. 1. Problem
  2. 2. Sample input
  3. 3. Sample output
  4. 4. Solution

Problem

At least it’s not a sudoku problem

The puzzle Nurikabe is played on a grid. Initially, each grid space is either blank or contains a single number. The goal is to shade in some of the blank spaces to satisfy the following constraints:

  • Any two shaded spaces are connected by some sequence of adjacent shaded spaces. Two spaces are called adjacent if they share a side.
  • For each of the unshaded spaces b, let Wb be the collection of all unshaded spaces that can be reached from b by a sequence of adjacent unshaded spaces. Then, Wb contains exactly one numbered space and that number is exactly the number of spaces in Wb.
  • For any unshaded space b, there is a sequence of unshaded spaces starting at b and ending at a space on the edge of the grid where consecutive spaces in this sequence share a side or a corner.
  • Finally, in every 2 x 2 subsquare there is at least one unshaded space.

The image shows an example of a Nurikabe puzzle and its solution. Take care to verify all four constraints are satisfied in the solution. To help you understand the third constraint, note that the middle cell containing the number 1 can reach the edge of the grid since it shares a corner with a group of unshaded spaces containing the number 2.

Example Nurikabe

It is known that the problem of determining if a Nurikabe grid can be shaded to satisfy the constraints is NP-complete. Your task is much easier. Given an initial grid and a proposed shading, determine if the shading satisfies the constraints of the Nurikabe puzzle.

Input begins with a single integer t that indicates the number of grids to verify. The first line of each case contains three integers r,c,d where the grid has r rows and c columns (1 ≤ r,c ≤ 100). Then, d lines follow, each containing three integers r’,c’,n meaning the grid cell at location (r’,c’) contains the positive number n. The upper-left grid space has coordinates (0,0), no space receives more than one number, and no two numbered grid spaces will share an edge. Finally, the shading data is specified by r strings of c characters each (one string per line). The j’th character in the i’th row of the shading data is ‘#’ if the cell with coordinates (i,j) is shaded and ‘.’ if that cell is not shaded. Each test case is preceded by a blank line.

For each input case, output a line containing either solved or not solved to indicate whether or not the shading represents a solution to the puzzle.

Sample input

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
5
5 5 6
0 0 3
0 2 1
0 4 2
2 2 1
3 4 2
4 0 2
.#.#.
.###.
.#.##
###..
..###
5 5 6
0 0 3
0 2 1
0 4 2
2 2 1
3 4 3
4 0 2
.#.#.
.###.
.#.##
####.
..#..
2 3 1
0 0 2
.##
.##
2 2 1
0 0 1
..
##
2 2 2
0 0 1
1 1 1
.#
#.

Sample output

1
2
3
4
5
solved
not solved
not solved
not solved
not solved

Solution

題目描述：

  • 所有陰影區域會相連 (上下左右)
  • 每一個區域的數字，會恰好等於該區域的非陰影個數。
  • 所有非陰影的區域，皆可以連到遊戲盤面的四邊 (九宮格連接)
  • 任意 2x2 區域，至少有一個非陰影的區域。

題目解法：

能剪枝就剪枝，不然很容易 TLE。討論版面上說 DFS 比 BFS 快一些。但這裡還是用 BFS 完成。

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
int g[205][205], ug[205][205];
char pattern[205][205];
int cond1(int x, int y, int r, int c, int cellcnt) {
/* 
 Any two shaded spaces are connected by some sequence 
 of adjacent shaded spaces. Two spaces are called 
 adjacent if they share a side. 
*/
    int dx[] = {0,0,1,-1};
    int dy[] = {1,-1,0,0};
    queue<int> X, Y;
    int i, tx, ty;
    char used[205][205] = {};
    X.push(x), Y.push(y);
    used[x][y] = 1;
    cellcnt--;
    while(!X.empty()) {
        x = X.front(), X.pop();
        y = Y.front(), Y.pop();
        for(i = 0; i < 4; i++) {
            tx = x+dx[i], ty = y+dy[i];
            if(tx < 0 || ty < 0 || tx >= r || ty >= c)
                continue;
            if(used[tx][ty] == 0 && pattern[tx][ty] == '#') {
                used[tx][ty] = 1;
                cellcnt--;
                if(cellcnt < 0)	return 0;
                X.push(tx), Y.push(ty);
            }
        }
    }
    return cellcnt == 0;
}
int cond2(int x, int y, int r, int c) {
/*
 For each of the unshaded spaces b, let Wb be the 
 collection of all unshaded spaces that can be 
 reached from b by a sequence of adjacent unshaded 
 spaces. Then, Wb contains exactly one numbered 
 space and that number is exactly the number of 
 spaces in Wb. 
*/
    int dx[] = {0,0,1,-1};
    int dy[] = {1,-1,0,0};
    queue<int> X, Y;
    int Wb = g[x][y], i, tx, ty;
    char used[205][205] = {};
    if(pattern[x][y] == '.') {
        X.push(x), Y.push(y);
        used[x][y] = 1;
    } else
        return 0;
    Wb--;
    while(!X.empty()) {
        x = X.front(), X.pop();
        y = Y.front(), Y.pop();
        for(i = 0; i < 4; i++) {
            tx = x+dx[i], ty = y+dy[i];
            if(tx < 0 || ty < 0 || tx >= r || ty >= c)
                continue;
            if(used[tx][ty] == 0 && pattern[tx][ty] == '.') {
                // if(ug[tx][ty]) return 0; // other Wb
                used[tx][ty] = 1;
                Wb--;
                if(Wb < 0) return 0;
                X.push(tx), Y.push(ty);
            }
        }
    }
    return Wb == 0;
}
int cond3(int x, int y, int r, int c) {
/*
  For any unshaded space b, there is a sequence 
  of unshaded spaces starting at b and ending 
  at a space on the edge of the grid where 
  consecutive spaces in this sequence share a 
  side or a corner. 
*/
    int dx[] = {0, 0, 1, 1, 1, -1, -1, -1};
    int dy[] = {1, -1, 0, 1, -1, 0, 1, -1};
    queue<int> X, Y;
    int i, tx, ty;
    char used[205][205] = {};
    if(pattern[x][y] != '.')
        return 1;
    X.push(x), Y.push(y);
    used[x][y] = 1;
    while(!X.empty()) {
        x = X.front(), X.pop();
        y = Y.front(), Y.pop();
        if(x == 0 || x == r-1 || y == 0 || y == c-1)
            return 1;
        for(i = 0; i < 8; i++) {
            tx = x+dx[i], ty = y+dy[i];
            if(tx < 0 || ty < 0 || tx >= r || ty >= c)
                continue;
            if(used[tx][ty] == 0 && pattern[tx][ty] == '.') {
                used[tx][ty] = 1;
                X.push(tx), Y.push(ty);
            }
        }
    }
    return 0;
}
int cond4(int r, int c) {
    int i, j;
    for(i = 0; i < r-1; i++) {
        for(j = 0; j < c-1; j++) {
            bool flag = (pattern[i][j] == '.' || pattern[i][j+1] == '.' ||
                         pattern[i+1][j] == '.' || pattern[i+1][j+1] == '.');
            if(flag == false)
                return 0;
        }
    }
    return 1;
}
int main() {
    // freopen("in.txt", "r+t", stdin);
    // freopen("out.txt", "w+t", stdout); 
    int testcase;
    int r, c, n;
    int x, y, v, i, j, k;
    scanf("%d", &testcase);
    while(testcase--) {
        if(scanf("%d %d %d", &r, &c, &n) != 3)
            return 0;
        memset(g, 0, sizeof(g));
        memset(ug, 0, sizeof(ug));
        int tot = 0;
        int ret = 1;
        for(i = 0; i < n; i++) {
            scanf("%d %d %d", &x, &y, &v);
            g[x][y] = v;
            ug[x][y] = 1;
            tot += v;
        }
        for(i = 0; i < r; i++)
            scanf("%s", &pattern[i]);
        int cellcnt = 0;
        int unshaded = 0;
        for(i = 0; i < r; i++)
            for(j = 0; j < c; j++)
                if(pattern[i][j] == '#')
                    cellcnt++, x = i, y = j;
                else
                    unshaded++;
        if(tot != unshaded) {
            puts("not solved");
            continue;
        }
        if(cellcnt && !cond1(x, y, r, c, cellcnt)) {
            puts("not solved");
            continue;
        }
        for(i = 0; i < r && ret; i++) {
            for(j = 0; j < c && ret; j++) {
                if(ug[i][j]) {
                    ret &= cond2(i, j, r, c);
                }
            }
        }
        if(!ret) {
            puts("not solved");
            continue;
        }
        for(i = 0; i < r && ret; i++) {
            for(j = 0; j < c && ret; j++) {
                if(ug[i][j]) {
                    ret &= cond3(i, j, r, c);
                }
            }
        }
        if(!ret) {
            puts("not solved");
            continue;
        }
        ret &= cond4(r, c);
        if(!ret) {
            puts("not solved");
            continue;
        }
        puts("solved");
    }
    return 0;
}