解題區►解題區 - UVa

UVa 11376 - Tilt!

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution
    1. 4.1. IDA*

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
*/