解題區/解題區 - UVa

UVa 11931 - Maze Escape

Problem

類似倉庫番遊戲，必須將箱子推到指定的按鈕位置，才會開啟逃離門，每一次可以走一步，如果箱子在旁邊，則人與箱子會同時往同一個方向移動。求逃離最少步數。

在還沒有打開門之前，門就相當於障礙物存在，不能經過。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
3 3
d.b
.@.
x.#
3 5
...d.
.#x#.
...@b
0 0

Sample Output

1
2
No Way!
20

Solution

反例輸出有誤，把 No Way! 拆成兩行送出結果拿到 WA。

把人的位置和箱子位置記錄成一個狀態，得到 dist[sx][sy][bx][by] 進行 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
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
int sx, sy, ex, ey, bx, by, cx, cy;
int n, m;
char g[32][32];
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int dist[25][25][25][25];
int bfs() {
    memset(dist, 0, sizeof(dist));
    dist[sx][sy][bx][by] = 1;
    queue<int> X, Y, BX, BY;
    int x, y, tx, ty, ttx, tty;
    X.push(sx), Y.push(sy), BX.push(bx), BY.push(by);
    while (!X.empty()) {
        x = X.front(), X.pop();
        y = Y.front(), Y.pop();
        bx = BX.front(), BX.pop();
        by = BY.front(), BY.pop();
        int step = dist[x][y][bx][by];
        for (int i = 0; i < 4; i++) {
            tx = x + dx[i], ty = y + dy[i];
            if (tx < 0 || ty < 0 || tx >= n || ty >= m)
                continue;
            if (g[tx][ty] == 'd' && g[bx][by] == 'b')
                return step;
            if (g[tx][ty] == '#' || g[tx][ty] == 'd')
                continue;
            if (tx == bx && ty == by) { // push it
                ttx = tx + dx[i], tty = ty + dy[i];
                if (ttx < 0 || tty < 0 || ttx >= n || tty >= m)
                    continue;
                if (g[ttx][tty] == '#' || g[ttx][tty] == 'd')
                    continue;
                if (dist[tx][ty][ttx][tty] == 0) {
                    dist[tx][ty][ttx][tty] = step + 1;
                    X.push(tx), Y.push(ty), BX.push(ttx), BY.push(tty);
                }
            } else {
                if (dist[tx][ty][bx][by] == 0) {
                    dist[tx][ty][bx][by] = step + 1;
                    X.push(tx), Y.push(ty), BX.push(bx), BY.push(by);
                }
            }
        }
    }
    return -1;
}
int main() {
    while (scanf("%d %d", &n, &m) == 2 && n) {
        for (int i = 0; i < n; i++)
            scanf("%s", g[i]);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == '@')
                    sx = i, sy = j;
                if (g[i][j] == 'd')
                    ex = i, ey = j;
                if (g[i][j] == 'x')
                    bx = i, by = j;
                if (g[i][j] == 'b')
                    cx = i, cy = j;
            }
        }
        int ret = bfs();
        if (ret < 0)	
            puts("No Way!");
        else
            printf("%d\n", ret);
    }
    return 0;
}
/*
3 3
d.b
.@.
x.#
3 5
...d.
.#x#.
...@b
0 0
*/
Read More +
解題區/解題區 - UVa

UVa 11669 - Non Decreasing Prime Sequence

Problem

每一個數字可以做質因數分解，找尋區間 [l, r] 所有數字質因數分解後，字典順序第 k 小的結果。

字典順序先按照集合個數由小到大，相同時才按照一般字典順序排序。

Sample Input

1
2
3
4
3
2 10 1
2 10 5
2 10 9

Sample Output

1
2
3
Case 1: 2
Case 2: 2 2
Case 3: 2 2 2

Solution

首先必須建質數表，之後利用 dfs 搜索出字典順序的結果，特別小心 overflow 的計算，必須使用 long long 防止在 1000000 以內的數字相乘溢位。

之後可以得到每一個數字質因數分解之後的排序結果 rank[i] = number, arank[number] = i。

然而每一組詢問，相當於在 arank 中查找 [l, r] 的第 k 小數字為何，輸出其 number 的結果。

套用區間第 k 大的解法，在離線情況下 (不更動元素)，按照順序插入 rank[number]，在 O(n log n) 時間內建表，消耗 O(n log n) 空間，在 O(log n) 回答。

在回答方面比歸併樹或者是塊狀鏈表快很多，可惜的是空間消耗相當驚人。

現在學到了一種可持久化的數據精神，有一種為函數式線段樹，最簡單理解的就是採用修改不改值，而是增加新的節點，而每一次修改最多增加 O(n log n) (延著線段樹走訪路徑增加節點)

也就是說，每一次修改會根據前一次的 root 增加一個新的 root’，這是一個相當重要的一環，每一次修改會產生新的一棵線段樹，而這個新線段樹大部分節點會使用前一個線段樹的節點，因此只要針對走訪不影響的情況下，我們仍然會經過舊有的節點。

為了找到區間 K 大，使用函數式線段樹有點類似於掃描線算法，對於某個時間點依序將數字放進去，然後對於區間查詢 K 大的時候，相當於對某個時間點之間作減法運算。

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <assert.h>
using namespace std;
struct Node {
    int l, r, lson, rson;
    int sum;
} node[1048576 * 23];
int nodesize = 0;
int root[1048576];
int build(int l, int r) {
    if (l > r)  return 0;
    int k = nodesize++;
    node[k].l = l, node[k].r = r, node[k].sum = 0;
    node[k].lson = node[k].rson = 0;
    if (l == r) return k;
    int m = (l + r)/2;
    node[k].lson = build(l, m);
    node[k].rson = build(m+1, r);
    return k;
}
int change(int p, int x, int val) {
    int k = nodesize++;
    node[k] = node[p];
    node[k].sum += val;
    if (node[k].l == node[k].r) return k;
    int m = (node[k].l + node[k].r)/2;
    if (x <= m)
        node[k].lson = change(node[p].lson, x, val);
    else
        node[k].rson = change(node[p].rson, x, val);
    return k;
}
int query(int tp, int tq, int k) {
    if (node[tp].l == node[tp].r)
        return node[tp].l;
    int t = node[node[tp].lson].sum - node[node[tq].lson].sum;
    if (k <= t)
        return query(node[tp].lson, node[tq].lson, k);
    else
        return query(node[tp].rson, node[tq].rson, k - t);
}
#define maxL (1000000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[maxL];
int P[100000], Pt = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 1000000;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            for (k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
            P[Pt++] = i;
        }
    }
}
int fpath[30];
int rank[1048576], arank[1048576], ridx = 0;
void dfsBuild(int idx, long long v, int mxdep, int dep) {
    if (dep == mxdep) {
        rank[v] = ++ridx;
        arank[ridx] = v;
        return ;
    } 
    for (int i = idx; i < Pt && v * P[i] <= 1000000; i++)
        fpath[dep] = P[i], dfsBuild(i, v * P[i], mxdep, dep+1);
}
void printfactor(int n) {
    for(int i = 0, j; i < Pt && P[i] * P[i] <= n; i++) {
        if(n%P[i] == 0) {
            for(j = 0; n%P[i] == 0; n /= P[i], j++)
                printf(" %d", P[i]);
        }		
    }
    if (n != 1)	printf(" %d", n);
    puts("");
}
int main() {
    sieve();
    for (int i = 1; i < 20; i++)
        dfsBuild(0, 1, i, 0);    
            
    nodesize = 1;
    root[0] = build(1, 1000000);        
    for (int i = 1; i <= 1000000; i++) {
        if (rank[i])
        	root[i] = change(root[i-1], rank[i], 1);
        else
        	root[i] = root[i-1];
    }
    
    int testcase, cases = 0, x, y, k;
    scanf("%d", &testcase);
    while (testcase--) {
    	scanf("%d %d %d", &x, &y, &k);
    	int ret = arank[query(root[y], root[x-1], k)];
    	printf("Case %d:", ++cases);
        printfactor(ret);
    }
    return 0;
}
/*
 7 3
 1 5 2 6 3 7 4
 2 5 3
 4 4 1
 1 7 3
 */
Read More +
解題區/解題區 - UVa

UVa 11501 - Laurel Creek

Problem

在淹水的平台上，有不少樹樁 (stump) 和漂浮的圓木 (log)，可以經由圓木到另一個樹樁，請問最少要幾個操作才能從起點樹樁到終點樹樁。

操作：

  • 根據相鄰的圓木，移動到下一個樹樁。
  • 撿起某一個方向的相鄰圓木，身上最多拿著一個圓木。
  • 往另一個方向放置圓木，並且另一端要恰好接著樹樁。

給定的圓木會有多個 | 或者是 - 連接在一起表示同一個圓木。

Sample Input

1
2
3
4
5
6
7
8
9
1
7 11
....S......
....|......
B---S......
...........
...........
...........
....S.S...E

Sample Output

1
10

Solution

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
int n, m;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
struct state {
    char g[17][17];
    int x, y, log;
    bool operator<(const state &a) const {
        if (x != a.x)	return x < a.x;
        if (y != a.y)	return y < a.y;
        if (log != a.log)	return log < a.log;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (g[i][j] != a.g[i][j])
                    return g[i][j] < a.g[i][j];
        return false;
    }
    void print() {
        for (int i = 0; i < n; i++, puts("")) {
            for (int j = 0; j < m; j++) {
                if (i == x && j == y)	printf("!");
                else	printf("%c", g[i][j]);
            }
        }
        printf("log %d\n", log);
        puts("--");
    }
};
int isValid(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}
int bfs(state init) {
    state u, v;
    queue<state> Q;
    map<state, int> R;
    int tx, ty;
    Q.push(init), R[init] = 0;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        int step = R[u];
        if (u.g[u.x][u.y] == 'E')
            return step;	
//		u.print(), getchar();
        for (int i = 0; i < 4; i++) { // traverse
            tx = u.x + dx[i], ty = u.y + dy[i];
            while (isValid(tx, ty) && u.g[tx][ty] != '.') {
                if (u.g[tx][ty] == 'S' || u.g[tx][ty] == 'B' || u.g[tx][ty] == 'E') {
                    v = u, v.x = tx, v.y = ty;
                    if (R.find(v) == R.end()) {
                        R[v] = step + 1;
                        Q.push(v);
                    }
                    break;
                }
                if (i < 2 && u.g[tx][ty] != '-')	break;
                if (i > 1 && u.g[tx][ty] != '|')	break;
                tx += dx[i], ty += dy[i];
            }
        }
        if (u.log == 0) { // pick up
            for (int i = 0; i < 4; i++) {
                tx = u.x + dx[i], ty = u.y + dy[i];
                if (isValid(tx, ty) && ((i < 2 && u.g[tx][ty] == '-') || (i > 1 && u.g[tx][ty] == '|'))) {
                    v = u;
                    while (isValid(tx, ty) && u.g[tx][ty] != '.') {
                        if (u.g[tx][ty] == 'S' || u.g[tx][ty] == 'B' || u.g[tx][ty] == 'E') {
                            if (R.find(v) == R.end()) {
                                R[v] = step + 1;
                                Q.push(v);
                            }
                            break;
                        }
                        v.g[tx][ty] = '.', v.log++;
                        if (i < 2 && u.g[tx][ty] != '-')	break;
                        if (i > 1 && u.g[tx][ty] != '|')	break;
                        tx += dx[i], ty += dy[i];						
                    }
                }
            }
        } else { // put down.
            for (int i = 0; i < 4; i++) {
                tx = u.x + dx[i], ty = u.y + dy[i];
                if (isValid(tx, ty) && u.g[tx][ty] == '.') {
                    int dist = 0;
                    while (isValid(tx, ty)) {
                        if (u.g[tx][ty] == 'S' || u.g[tx][ty] == 'B' || u.g[tx][ty] == 'E') {
                            v = u;
                            if (dist == u.log) {
                                v.log = 0;
                                tx = u.x + dx[i], ty = u.y + dy[i];
                                while (isValid(tx, ty) && u.g[tx][ty] == '.') {
                                    if (u.g[tx][ty] == 'S' || u.g[tx][ty] == 'B' || u.g[tx][ty] == 'E')
                                        break;
                                    if (i < 2)	v.g[tx][ty] = '-';
                                    if (i > 1)	v.g[tx][ty] = '|';
                                    tx += dx[i], ty += dy[i];
                                }
                                if (R.find(v) == R.end()) {
                                    R[v] = step + 1;
                                    Q.push(v);
                                }
                            }
                            break;
                        }
                        if (u.g[tx][ty] != '.')	break;
                        dist++;
                        tx += dx[i], ty += dy[i];
                    }
                }
            }
        }
    }
    return 0;
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        state init, u, v;
        for (int i = 0; i < n; i++)
            scanf("%s", init.g[i]);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (init.g[i][j] == 'B')
                    init.x = i, init.y = j, init.log = 0;
            }
        }
        int ret = bfs(init);
        printf("%d\n", ret);
    }
    return 0;
}
/*
999
7 11
....S......
....|......
B---S......
...........
...........
...........
....S.S...E
4 4
....
.B.S
.|..
...E
7 11
....S...S..
........|..
B-----S.|.E
......|.|..
......|.S..
......|....
....S-S....
4 4
....
S-B.
....
..E.
*/
Read More +
解題區/解題區 - UVa

UVa 11376 - Tilt!

Problem

滾球遊戲，一顆紅球在迷宮中滾動要收集到所有藍色球球 (藍色球球最多 25 顆)，求滾動的傾斜次數最少。每一次將盤面傾斜，紅球必須滾到該方向的最底部，能滾就必須繼續往方向滾過去。

Sample Input

1
2
3
4
5
6
7
8
9
5
9AC9C
18006
5120C
12806
3A63E
1 1
5 5
0

Sample Output

1
ESWNENWSE

Solution

這題說不定 bfs 就可以過，被蘿莉控的文字欺騙寫了不純正的 IDA，IDA 原則上不會記錄任何搜索狀態，否則就跟 A* 一樣，然而這一題多卡一個狀態紀錄，就這麼 AC，並且拿到 Rank 6，速度還挺快的。

狀態：當前紅球所在位置、已經得到的藍球 (壓縮在一個 32bits 內)

估價函數：當前位置到剩餘藍球的最少步數的最大值

預處理每一個位置滾動的下一個位置，減少過程中模擬的時間。

單純的 IDA* 無法通過，在討論區的測資也要跑很久，隨後加搜索過程中的狀態紀錄，速度可以說飛快。但是由於深度加深的處理，每一次必須清空搜索紀錄，稍微比 bfs 好點的地方只在於利用啟發式的估價函數砍不少狀態紀錄。

IDA*

迭代加深搜索，由於 dfs 會深度優先，會導致搜索深度太深而無法找到最少、最佳解，因此根據搜索時的估價函數，慢慢鬆弛可以搜索的限制深度。

這方面很類似 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
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
#include <stdio.h>
#include <string.h>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
char g[16][16];
int bg[16][16], dirg[16][16][4][3], blueAll, blueCnt;
int short_path[16][16][32];
const int dx[] = {0, -1, 1, 0};
const int dy[] = {1, 0, 0, -1};
const int dmask[] = {4, 8, 2, 1};
const char dstr[] = "ENSW";
void buildDirg(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < 4; k++) {
                int blue = 0;
                int sx = i, sy = j;
                while (true) {
                    if (bg[sx][sy])
                        blue |= 1<<(bg[sx][sy]-1);
                    if (g[sx][sy]&dmask[k])
                        break;
                    sx += dx[k], sy += dy[k];
                }
                dirg[i][j][k][0] = sx;
                dirg[i][j][k][1] = sy;
                dirg[i][j][k][2] = blue;
            }
        }
    }
}
void buildHfun(int n) {
    memset(short_path, 0x3f, sizeof(short_path));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            queue<int> X, Y;
            int dist[16][16], sx, sy, tx, ty;
            memset(dist, 0x3f, sizeof(dist));
            X.push(i), Y.push(j), dist[i][j] = 0;
            if (bg[i][j])
                short_path[i][j][bg[i][j]-1] = min(short_path[i][j][bg[i][j]-1], 0);
            while (!X.empty()) {
                sx = X.front(), X.pop();
                sy = Y.front(), Y.pop();
                for (int p = 0; p < 4; p++) {
                    tx = sx, ty = sy;
                    while (true) {
                        if (bg[tx][ty])	
                            short_path[i][j][bg[tx][ty]-1] = min(short_path[i][j][bg[tx][ty]-1], dist[sx][sy] + 1);
                        if (g[tx][ty]&dmask[p])
                            break;
                        tx += dx[p], ty += dy[p];
                    }						
                    if (dist[tx][ty] > dist[sx][sy] + 1) {
                        dist[tx][ty] = dist[sx][sy] + 1;
                        X.push(tx), Y.push(ty);
                    }
                }
            }
        }
    }
}
int ida_dep, solved;
char path[1024];
int H(int sx, int sy, int bstate) {
    int ret = 0;
    for (int i = 0; i < blueCnt; i++) {
        if ((bstate>>i)&1)	continue;
        ret = max(ret, short_path[sx][sy][i]);
    }
    return ret;
}
map<int, int> record[16][16]; // [sx][sy][bstate] = minstep
int IDA(int sx, int sy, int bstate, int dep, int hv, int dlast) {
    if (hv == 0) {
        path[dep] = '\0';
        puts(path);
        solved = dep;
        return dep;
    }
    if (dep + hv > ida_dep)	return dep + hv;
    
    map<int, int>::iterator it = record[sx][sy].find(bstate);
    if (it == record[sx][sy].end())
        record[sx][sy][bstate] = dep;
    else {
        if (it->second <= dep)	return 0x3f3f3f3f;
        else					it->second = dep;
    }
    
    int ret = 0x3f3f3f3f, shv, tmp;
    for (int i = 0; i < 4; i++) {
        if (i == dlast)	continue;
        path[dep] = dstr[i];
        shv = H(dirg[sx][sy][i][0], dirg[sx][sy][i][1], bstate|dirg[sx][sy][i][2]);
        tmp = IDA(dirg[sx][sy][i][0], dirg[sx][sy][i][1], bstate|dirg[sx][sy][i][2], dep+1, shv, i);
        if (solved)	return solved;
        ret = min(ret, tmp);
    }
    return ret;
}
int main() {
    int n, next_n, sx, sy, ex, ey;
    char s[1024];
    scanf("%d", &n);
    while (n) {
        for (int i = 0; i < n; i++)
            scanf("%s", g[i]);
        scanf("%d %d", &sx, &sy);
        sx--, sy--;
        memset(bg, 0, sizeof(bg));
        while (getchar() != '\n');
        while (gets(s)) {
            if (sscanf(s, "%d %d", &ex, &ey) == 2) {
                ex--, ey--;
                bg[ex][ey] = 1;
            } else if (sscanf(s, "%d", &next_n) == 1)
                break;
        }
        blueAll = blueCnt = 0;
        int bx[128], by[128];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (bg[i][j]) {
                    bx[blueCnt] = i, by[blueCnt] = j;
                    blueCnt++, bg[i][j] = blueCnt, blueAll |= 1<<(blueCnt-1);
                }
                if ('0' <= g[i][j] && g[i][j] <= '9')
                    g[i][j] -= '0';
                else if(g[i][j] >= 'A' && g[i][j] <= 'Z')
                    g[i][j] = g[i][j] - 'A' + 10;
            }
        }
        
        buildDirg(n);
        buildHfun(n);
        
//		for (int i = 0; i < n; i++) {
//			for (int j = 0; j < n; j++) {
//				for (int k = 0; k < blueCnt; k++) {
//					printf("%d %d to %d %d = %d\n", i, j, bx[k], by[k], short_path[i][j][k]);
//				}
//			}
//		}
        
        int bstate = 0;
        if (bg[sx][sy])	bstate = 1<<(bg[sx][sy]-1);
        int initH = H(sx, sy, bstate);
        if (initH == 0) {
            puts("SOLVED");
        } else {
            solved = 0;
            ida_dep = initH;
            while (solved == 0) {
                ida_dep = IDA(sx, sy, bstate, 0, initH, 4);
                for (int i = 0; i < n; i++) // not tradition ida*
                    for (int j = 0; j < n; j++)
                        record[i][j].clear();
            }
        }
        n = next_n;
    }
    return 0;
}
/*
5
9AC9C
18006
5120C
12806
3A63E
1 1
5 5
0
8
9A88CB8C
18610824
30804184
90430004
10080457
1430000C
53800245
3A263A26
6 4
4 1
8 1
2 2
7 3
4 4
1 5
7 5
5 6
3 7
8 7
2 8
4 8
6
98E98E
30A00C
908047
10430C
710804
B63677
4 1
1 3
3 6
5
9AC9C
18006
5120C
12806
3A63E
1 1
5 5
0
*/
Read More +
解題區/解題區 - UVa

UVa 11052 - Economic phone calls

Problem

給一台手機的通話紀錄，通話紀錄分成兩類，其中一類標記為 + 表示重要訊息，另一類標記為 - 表示不重要訊息。手機中的歷史紀錄時間不會紀錄年份，靠著有順序的嚴格遞增表示同一年。

假使現在只想要知道 + 的所有電話紀錄發現在哪一年份，可以忽略部分的 - 來推估每一通電話的年份，請問最少要保留幾份紀錄。

每一組的最後一筆測資表示現在年份。

Sample Input

1
2
3
4
5
6
7
8
9
7
12:31:23:59 0123456789012345 +
07:21:19:00 1337 -
01:01:00:00 0987654321 -
07:21:14:00 1337 -
11:11:11:11 11111111111 +
01:01:00:00 0123456789 +
01:01:00:00 0987654321 -
0

Sample Output

1
6

Solution

可以推測，從現在到最早期的 + 紀錄之間的每一年至少需要一通電話。

首先將輸入的每一通電話算出年份，然後找到需要回溯的最早期電話，在這更之前的電話紀錄就可以無視，推算時間與更早期的紀錄無關。

定義 dp[i] 表示第 i 筆電話紀錄後，能夠使得 [i, n] 之間 + 紀錄回溯年代的最少紀錄筆數。

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
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
    int n;
    int time[1024];
    char mark[1024][4];
    while (scanf("%d", &n) == 1 && n) {
        int mm, dd, HH, MM;
        for (int i = 0; i < n; i++) {
            scanf("%d:%d:%d:%d %*s %s", &mm, &dd, &HH, &MM, mark[i]);
            time[i] = ((mm * 31 + dd) * 24 + HH) * 60 + MM;
        }
        int year[1024] = {}, cur_year;
        for (int i = 1; i < n; i++) {
            if (time[i] <= time[i-1])
                year[i] = year[i-1] + 1;
            else
                year[i] = year[i-1];
            cur_year = year[i];
        }
        int dp[1024] = {}, last = -1, trace = -1;
        // dp[i] : record i satisfy that all `+` record can trace in year[i]~cur_year
        for (int i = n - 1; i >= 0; i--) {
            if (last == -1 && year[i] == cur_year)
                dp[i] = 1; 		// record now time.
            else
                dp[i] = n - i; 	// record all after this. (init value)
            if (last == -1 && (mark[i][0] == '+' || year[i] != cur_year))
                last = i;
            if (mark[i][0] == '+')
                trace = i;
        }
        for (int i = last; i >= trace; i--) {
            for (int j = i + 1; j < n; j++) {
                if (year[i] == year[j])
                    dp[i] = min(dp[i], dp[j] + 1);
                else if (time[i] >= time[j] && year[j] - year[i] == 1)
                    dp[i] = min(dp[i], dp[j] + 1);
                else
                    break;
                if (mark[j][0] == '+')	break;
            }
        }
//		for (int i = 0; i < n; i++)
//			printf("[%d] y %d dp %d\n", i, year[i], dp[i]);
//		printf("%d %d\n", last, trace);
        printf("%d\n", dp[trace]);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 10841 - Lift Hopping in the Real World

Problem

在一棟高樓中有 N 台電梯，每個電梯停靠的樓層有所限制，同時每一台電梯在相鄰樓層移動的所需時間也不同。轉換電梯 (出電梯) 需要 5 秒的時間，然後可以轉搭其他電梯。並不曉得一開始電梯停靠在那一個樓層，即使下了電梯也要等待電梯移動到該層。

請問從 0 樓到 K 樓的最少時間為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2 30
10 5
0 1 3 5 7 9 11 13 15 20 99
4 13 15 19 20 25 30
2 30
10 1
0 5 10 12 14 20 25 30
2 4 6 8 10 12 14 22 25 28 29
3 50
10 50 100
0 10 30 40
0 20 30
0 20 50
1 1
2
0 2 4 6 8 10

Sample Output

1
2
3
4
1295
600
8505
IMPOSSIBLE

Solution

很明顯地，把每一個樓層當節點，可以根據電梯的移動建造邊，邊與邊之間的轉換必須多 5 花費以及電梯在最慘情況下移動到該層的花費。

電梯在最慘情況下移動到該層的花費 : 電梯在最高樓層或者是最低樓層停靠，收到指令後移動到該層。

直接對其使用最短路即可。

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
#include <stdio.h> 
#include <vector>
#include <queue> 
#include <algorithm>
#include <sstream>
using namespace std;
struct edge {
    int to, v, label;
    edge(int a=0, int b=0, int c=0):
        to(a), v(b), label(c){}
};
vector<edge> g[128];
int mxfloor[128], mnfloor[128], T[128];
int dist[128], inq[128];
void spfa(int N, int K) {
    for (int i = 0; i < 128; i++)
        dist[i] = 0x3f3f3f3f;
    int u, v, w, l;
    queue<int> Q;
    Q.push(0), dist[0] = 0;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        inq[u] = 0;
        for (int i = 0; i < g[u].size(); i++) {
            v = g[u][i].to, l = g[u][i].label;
            w = g[u][i].v + T[l] * max(mxfloor[l] - u, u - mnfloor[l]) + 5;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!inq[v]) {
                    inq[v] = 1;
                    Q.push(v);
                }
            }
        }
    }
    if (dist[K] == 0x3f3f3f3f)
        puts("IMPOSSIBLE");
    else
        printf("%d\n", K == 0 ? 0 : (dist[K] - 5));
}
int main() {
    int N, K, f[128];
    char s[1024];
    while (scanf("%d %d", &N, &K) == 2) {
        for (int i = 0; i < N; i++)
            scanf("%d", &T[i]);
        for (int i = 0; i < 128; i++)
            g[i].clear();
        while (getchar() != '\n');
        for (int i = 0; i < N; i++) {
            gets(s);
            stringstream sin(s);
            int n = 0;
            while (sin >> f[n])
                n++;
            mxfloor[i] = -1, mnfloor[i] = 0x3f3f3f3f;
            for (int j = 0; j < n; j++) {
                mxfloor[i] = max(mxfloor[i], f[j]);
                mnfloor[i] = min(mnfloor[i], f[j]);
                for (int k = 0; k < n; k++) {
                    if (j == k)	continue;
                    g[f[j]].push_back(edge(f[k], abs(f[k] - f[j]) * T[i], i));
                }
            }
        }
        spfa(N, K);
    }
    return 0;
}
/*
2 30
10 5
0 1 3 5 7 9 11 13 15 20 99
4 13 15 19 20 25 30
2 30
10 1
0 5 10 12 14 20 25 30
2 4 6 8 10 12 14 22 25 28 29
3 50
10 50 100
0 10 30 40
0 20 30
0 20 50
1 1
2
0 2 4 6 8 10
*/
Read More +
解題區/解題區 - UVa

UVa 10704 - Traffic!

Problem

一個華容道盤面，求最少步數。

水平的棋子只能水平移動、垂直的旗子只能垂直移動，移動一次的定義為按照可執行的方向移動數步，也就是說水平移動兩步、三步也只算一次移動。

Sample Input

1
2
3
4
5
6
1
2 1
1 4 0
3 1 0 1 3 0 5
2 0 0 4 4
1 5 2

Sample Output

1
The minimal number of moves to solve puzzle 1 is 8.

Solution

紀錄狀態整個棋盤盤面，做 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
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#include <stdio.h> 
#include <string.h>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
#define hash_mod 1000003
struct state {
    char g[6][6];
    unsigned int hash() {
        unsigned int a = 63689, b = 378551;
        unsigned int value = 0;
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 6; j++) {
                value = value * a + g[i][j];
                a *= b;
            }
        }
        return value % hash_mod;
    }
    bool operator<(const state &a) const {
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 6; j++) {
                if (g[i][j] != a.g[i][j])
                    return g[i][j] < a.g[i][j];
            }
        }
        return false;
    }
    void print() {
        for (int i = 0; i < 6; i++, puts(""))
            for (int j = 0; j < 6; j++)
                printf("%c", g[i][j]);
        puts("--");
    }
};
void color(state &s, int x, int y, int w, int h, char c) {
    for (int i = x; i < x + w; i++)
        for (int j = y; j < y + h; j++)
            s.g[i][j] = c;
}
map<state, int> hash[hash_mod];
state shiftup(state &u, int x, int y) {
    state v = u;
    char c = v.g[x][y];
    for (int i = 0; x+i < 6 && v.g[x+i][y] == c; i++)
        swap(v.g[x+i-1][y], v.g[x+i][y]);
    return v;
}
state shiftdown(state &u, int x, int y) {
    state v = u;
    char c = v.g[x][y];
    for (int i = 0; x+i >= 0 && v.g[x+i][y] == c; i--)
        swap(v.g[x+i+1][y], v.g[x+i][y]);
    return v;
}
state shiftleft(state &u, int x, int y) {
    state v = u;
    char c = v.g[x][y];
    for (int i = 0; y+i < 6 && v.g[x][y+i] == c; i++)
        swap(v.g[x][y+i-1], v.g[x][y+i]);
    return v;
}
state shiftright(state &u, int x, int y) {
    state v = u;
    char c = v.g[x][y];
    for (int i = 0; y+i >= 0 && v.g[x][y+i] == c; i--)
        swap(v.g[x][y+i+1], v.g[x][y+i]);
    return v;
}
int bfs(state init) {
    for (int i = 0; i < hash_mod; i++)
        hash[i].clear();
    int h = init.hash(), ti, tj;
    state u, v;
    queue<state> Q;
    Q.push(init), hash[h][init] = 0;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        h = u.hash();
        int step = hash[h][u];
        if (u.g[2][4] == 'w' && u.g[2][5] == 'w') {
//			u.print();
            return step;
        }
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 6; j++) {
                if (u.g[i][j] < 'a' || u.g[i][j] > 'z')
                    continue;
                ti = i, tj = j;
                v = u;
                while (ti-1 >= 0 && v.g[ti-1][tj] == ' ' && ti+1 < 6 && v.g[ti][tj] == v.g[ti+1][tj]) { // shift up
                    v = shiftup(v, ti, tj);
                    ti--;
                    h = v.hash();
                    if (hash[h].find(v) == hash[h].end()) {
                        hash[h][v] = step+1;
                        Q.push(v);
                    }
//					v.print();
                }
                ti = i, tj = j;
                v = u;
                while (ti-1 >= 0 && v.g[ti-1][tj] == v.g[ti][tj] && ti+1 < 6 && v.g[ti+1][tj] == ' ') { // shift down
                    v = shiftdown(v, ti, tj);
                    ti++;
                    h = v.hash();
                    if (hash[h].find(v) == hash[h].end()) {
                        hash[h][v] = step+1;
                        Q.push(v);
                    }
//					v.print();
                }
                ti = i, tj = j;
                v = u;
                while (tj-1 >= 0 && v.g[ti][tj-1] == ' ' && tj+1 < 6 && v.g[ti][tj] == v.g[ti][tj+1]) { // shift left
                    v = shiftleft(v, ti, tj);
                    tj--;
                    h = v.hash();
                    if (hash[h].find(v) == hash[h].end()) {
                        hash[h][v] = step+1;
                        Q.push(v);
                    }
//					v.print();
                }
                ti = i, tj = j;
                v = u;
                while (tj-1 >= 0 && v.g[ti][tj-1] == v.g[ti][tj] && tj+1 < 6 && v.g[ti][tj+1] == ' ') { // shift right
                    v = shiftright(v, ti, tj);
                    tj++;
                    h = v.hash();
                    if (hash[h].find(v) == hash[h].end()) {
                        hash[h][v] = step+1;
                        Q.push(v);
                    }
//					v.print();
                }
            }
        }
    }
    return -1;
}
int main() {
    int testcase, cases = 0;
    int wx, wy, n, x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        state init;
        char label = 'a';
        memset(init.g, ' ', sizeof(init.g));
        scanf("%d %d", &wx, &wy);
        color(init, wx, wy, 1, 2, 'w');
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &x, &y);
            color(init, x, y, 2, 1, label);
            label++;
        }
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &x, &y);
            color(init, x, y, 3, 1, label);
            label++;
        }
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &x, &y);
            color(init, x, y, 1, 2, label);
            label++;
        }
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &x, &y);
            color(init, x, y, 1, 3, label);
            label++;
        }
        int ret = bfs(init);
        printf("The minimal number of moves to solve puzzle %d is %d.\n", ++cases, ret);
    }
    return 0;
}
/*
1
2 1
1 4 0
3 1 0 1 3 0 5
2 0 0 4 4
1 5 2
99999
2 0
0
0
0
0
2 1
1 4 0
4 1 0 1 3 0 5 1 4
3 0 0 4 4 3 4
1 5 2
2 1
2 0 2 4 1
4 1 0 1 3 0 5 1 4
2 0 0 4 4
1 5 2
*/
Read More +
解題區/解題區 - UVa

UVa 932 - Checking the N-Queens Problem

Problem

給定一個 N * N 的棋盤，檢查 N 個皇后是否衝突，如果存有衝突，嘗試移動一個皇后 (根據他所在的位置進行移動)，如果可以有解則輸出，反之輸出找不到。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
5
00X00
X0000
000X0
0X000
0000X
5
0X000
X0000
000X0
0X000
0000X

Sample Output

1
2
3
4
5
6
7
8
9
YES
NO
YES
00X00
X0000
000X0
0X000
0000X

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
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int check(int qx[], int qy[], int n) {
    static int used[32] = {}, testcase = 0;
    testcase++;
    for (int i = 0; i < n; i++) {
        if (used[qx[i]] == testcase) return 0;
        used[qx[i]] = testcase;
    }
    testcase++;
    for (int i = 0; i < n; i++) {
        if (used[qy[i]] == testcase) return 0;
        used[qy[i]] = testcase;
    }
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (abs(qx[i] - qx[j]) == abs(qy[i] - qy[j]))
                return 0;
        }
    }
    return 1;
}
int main() {
    int n, cases = 0, tx, ty;
    char g[32][32];
    const int dx[] = {0, 0, 1, 1, 1, -1, -1, -1};
    const int dy[] = {1, -1, 0, 1, -1, 0, 1, -1};
    while (scanf("%d", &n) == 1) {
        if (cases++)	puts("");
        for (int i = 0; i < n; i++)
            scanf("%s", g[i]);
        int qx[32], qy[32], m = 0;
        for (int i = 0; i < n;i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] == 'X')
                    qx[m] = i, qy[m] = j, m++;
            }
        }
        if (check(qx, qy, m))
            puts("YES");
        else {
            puts("NO");
            int ok = 0;
            for (int i = 0; i < m && !ok; i++) {
                for (int j = 0; j < 8 && !ok; j++) {
                    tx = qx[i] + dx[j], ty = qy[i] + dy[j];
                    while (true) {
                        if (tx < 0 || ty < 0 || tx >= n || ty >= n)
                            break;
                        if (g[tx][ty] == '0') {
                            swap(tx, qx[i]), swap(ty, qy[i]);
                            if (check(qx, qy, m)) {
                                puts("YES");
                                ok = 1;
                                swap(g[qx[i]][qy[i]], g[tx][ty]);
                                for (int i = 0; i < n; i++)
                                    puts(g[i]);
                                break;
                            }
                            swap(tx, qx[i]), swap(ty, qy[i]);
                        }
                        tx += dx[j], ty += dy[j];
                    }
                }
            }
            if (!ok)
                puts("NO");
        }
    }
    return 0;
}
/*
5
00X00
X0000
000X0
0X000
0000X
5
0X000
X0000
000X0
0X000
0000X
*/
Read More +
解題區/解題區 - UVa

UVa 10838 - The Pawn Chess

Problem

在縮小版本國際象棋中，兩個人只能操控士兵 (Pawn)，其中白色先手並且位於棋盤下方，操控棋子為大寫 P，黑色後手為小寫 p。

士兵在移動時，只能往敵方軍營前進，只能往前一步走到空的，或者是吃掉對方斜著走。也就是當敵方在斜角時才能往斜角走。

將對方逼得無路可走時 (全滅)，或者是我方棋子抵達對方底線時遊戲宣告結束。請問白色先手最少要幾步才能獲勝？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
2
 
.ppp
....
.PPP
....
 
...p
...p
pP.P
...P

Sample Output

1
2
white (7)
black (2)

Solution

一種很傳統的博弈問題，一般而言對於劃分狀態最小化即可。但是效率會很差，因為狀態分化的太多，必須走訪所有的狀態才能知道結果。基於這一點，有了 alpha-beta 剪枝，但這種剪枝相當依賴走訪順序，因此也不保證是比較好的搜索，但已經提供相當不錯的思路。

pruning 中文翻譯：修剪

alpha-beta pruning

主要為博弈剪枝用，求最少步數獲勝 (對於是否必勝的判斷在效率上有待考量。)

策略

假設 [999, -999] 作為步數的決策 (用實際數值來假設)

  • 正數表示先手必勝的步數，越大表示需要的步數越少，
  • 負數表示後手必勝的步數，越小表示需要的步數越少。

根據博弈的遞迴寫法，步數從深度 999 往下找，先手要最大化其結果 (最後最少步數用 999 - 結果)，後手要最小化其結果 (最後最少步數用 999 + 結果)。分層討論的話，就是取最大 - 取最小 - 取最大 … 交錯。

我們把已知的兩個結果做討論，定義當前搜索過程中得到的 alpha 是先手最佳化，beta 是後手最佳化。

父節點會將已經找到的部分解傳遞給孩子繼續搜索，假使父親是取最大值，還是則都是要取最小值，如果其中一個孩子的最小值 p 已知，另一個孩子搜索到一半時，發現其中它的孩子回傳 q < p，其實可以放棄搜索，因為這一層還要取最小，隨後回父親要取最大，不可能比 p 還要大。直接放棄 son 的所有分支搜索。

1
2
3
4
5
  parent (first player maximum) alpha = maximum(p, son, ...)
 /     \
p      son (second player minimum) beta = minimum(q, ...)
       /
      q

發現思路其實相當簡單，關鍵在於如何表示最小化、最大化之間對於博弈的定義。

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
#include <stdio.h> 
#include <algorithm>
using namespace std;
struct state {
    char g[4][5];
    int isEnd() {
        int b = 0, w = 0;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++)  {
                if (g[i][j] == 'p')
                    b++;
                if (g[i][j] == 'P')
                    w++;
            }
        }
        if (b == 0 || w == 0)	return 1;
        for (int i = 0; i < 4; i++) {
            if (g[0][i] == 'P')	return 1;
            if (g[3][i] == 'p')	return 1;
        }
        return 0;
    }
};
int alpha_beta(state board, int depth, int alpha, int beta) {
    if (board.isEnd())
        return depth%2 == 0 ? -depth : depth;
    int movable = 0;
    if (depth%2 == 0) { // first player
        for (int i = 1; i < 4; i++)  {
            for (int j = 0; j < 4; j++) {
                if (board.g[i][j] == 'P') {
                    for (int k = j - 1; k <= j + 1; k++) {
                        if (k < 0 || k >= 4)
                            continue;
                        if ((k != j && board.g[i-1][k] == 'p') || (k == j && board.g[i-1][k] == '.')) {
                            state s = board;
                            s.g[i][j] = '.', s.g[i-1][k] = 'P';
                            alpha = max(alpha, alpha_beta(s, depth - 1, alpha, beta));
                            if (beta <= alpha)
                                return alpha;
                            movable = 1;
                        }
                    }
                }
            }
        }
        if (!movable)	return -depth;
        return alpha;
    } else {
        for (int i = 0; i < 3; i++)  {
            for (int j = 0; j < 4; j++) {
                if (board.g[i][j] == 'p') {
                    for (int k = j - 1; k <= j + 1; k++) {
                        if (k < 0 || k >= 4)
                            continue;
                        if ((k != j && board.g[i+1][k] == 'P') || (k == j && board.g[i+1][k] == '.')) {
                            state s = board;
                            s.g[i][j] = '.', s.g[i+1][k] = 'p';
                            beta = min(beta, alpha_beta(s, depth - 1, alpha, beta));
                            if (beta <= alpha)
                                return beta;
                            movable = 1;
                        }
                    }
                }
            }
        }
        if (!movable)	return depth;
        return beta;
    }
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        state init;
        for (int i = 0; i < 4; i++)
            scanf("%s", init.g[i]);
        int ret = alpha_beta(init, 36, -9999, 9999);
        if (ret >= 0)
            printf("white (%d)\n", 36 - ret);
        else
            printf("black (%d)\n", 36 + ret);
    }
    return 0;
}
/*
2
.ppp
....
.PPP
....
...p
...p
pP.P
...P
*/
Read More +
解題區/解題區 - UVa

UVa 12120 - Photographic Tour

Problem

每個攝影師必須從起點走到終點，中間搭乘時會消耗車票，並且每個攝影師都要按照主辦單位給定的車票順序使用，而車票的花費要恰好對應到搭乘花費。

請問有多少地點可以是攝影師經過的地方。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
3 2
0 1 1
0 2 2
3
1 1 2
3 2
0 1 1
0 2 2
1
1
0 0

Sample Output

1
2
Tour 1: 3
Tour 2: 0

Solution

紀錄兩個狀態，分別為起點到中繼點、中繼點到終點的結果。

起點到中繼點時，將記錄 dp1[i][j] 起點到中繼點 i，恰好使用第 j 張票。

終點到中繼點時，將記錄 dp2[i][j] 終點到中繼點 i，恰好使用第 n - j 張票。

隨後合併檢查是否中繼點可以構出一條路從起點到終點。

為了方便操作，將資料反轉丟入函數。

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
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector< pair<int, int> > g[1024];
void bfs(int u, int A[], int An, int rg[][128]) {
    int t;
    queue<int> Q, T;
    Q.push(u), T.push(0);
    rg[u][0] = 1;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        t = T.front(), T.pop();
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i].first;
            if (t < An && g[u][i].second == A[t]) {
                if (rg[v][t+1] == 0)  {
                    rg[v][t+1] = 1;
                    Q.push(v), T.push(t+1);
                }
            }
        }
    }
}
int main() {
    int n, m, t, cases = 0;
    int x, y, z, A[128]; 
    int g1[128][128], g2[128][128];
    while (scanf("%d %d", &n, &m) == 2 && n) {
        for (int i = 0; i < n; i++)
            g[i].clear();
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &x, &y, &z);
            g[x].push_back(make_pair(y, z));
            g[y].push_back(make_pair(x, z));
        }
        scanf("%d", &t);
        for (int i = 0; i < t; i++)
            scanf("%d", &A[i]);
        
        memset(g1, 0, sizeof(g1));
        memset(g2, 0, sizeof(g2));
        bfs(0, A, t, g1);
        reverse(A, A+t);
        bfs(n-1, A, t, g2);
        int ret = 0;
        for (int i = 0; i < n; i++) {
            int ok = 0;
            for (int j = 0; j <= t; j++)
                ok |= g1[i][j] && g2[i][t - j];
            ret += ok;
        }
        printf("Tour %d: %d\n", ++cases, ret);
    }
    return 0;
}
/*
3 2
0 1 1
0 2 2
3
1 1 2
3 2
0 1 1
0 2 2
1
1
0 0
*/
Read More +