解題區►解題區 - UVa

UVa 10463 - Aztec Knights

contents

  1. 1. Problem
  2. 2. Input
  3. 3. Output
  4. 4. Solution

Problem

給定一種特殊的騎士走法，請問在 n x m 格子上，從 (x, y) 到 (a, b) 的步數情況，走訪時不能重複經過相同點。

若能恰好在質數步抵達，輸出最少的步數。如不是質數，輸出合數的最少步數。都還是不行則輸出無法抵達。

Input

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

Output

1
2
3
CASE# 1: Destination is not reachable.
CASE# 2: The knight takes 2 prime moves.
CASE# 3: The knight takes 0 composite move(s).

Solution

這題麻煩的地方在於恰好在質數抵達，那麼考慮使用 IDA 來完成，在搜索時發生不是在質數步數抵達回傳無解，繼續迭代加深。估價函數為當前座標 (x, y) 到 (a, b) 的最短距離。

在做 IDA 之前，使用 Bfs 查看移動所需步數，若恰好是質數則直接輸出答案，若保證無法抵達終點，輸出無解。最後再進行 IDA 搜索，來加快處理程序。

根據測試，使用的質數步數不大於 11。

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
// IDA, Bfs
#include <stdio.h> 
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int dx[] = {1, 1, -1, -1, 3, 3, -3, -3};
const int dy[] = {3, -3, 3, -3, 1, -1, 1, -1};
const int px[] = {1, 1, -1, -1, 1, 1, -1, -1};
const int py[] = {1, -1, 1, -1, 1, -1, 1, -1};
int hdist[16][16][16][16];
vector< pair<int, int> > g[16][16];
int move(int n, int m, int x, int y, int kind, int &rx, int &ry) {
	int tx, ty;
	tx = x + dx[kind], ty = y + dy[kind];
	if (tx < 0 || ty < 0 || tx >= n || ty >= m)
		return 0;
	rx = tx, ry = ty;
	tx = x, ty = y;
//	for (int i = 0; i < 2; i++) {
//		tx = tx + px[kind], ty = ty + py[kind];
//		if (tx < 0 || ty < 0 || tx >= n || ty >= m)
//			return 0;
//	}
	return 1;
}
void moveBfs(int n, int m, int sx, int sy) {
	int x, y, tx, ty;
	int dist[16][16] = {};
	const int INF = 0x3f3f3f3f;
	queue<int> X, Y;
	
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			dist[i][j] = INF;
			
	X.push(sx), Y.push(sy), dist[sx][sy] = 0;
	while (!X.empty()) {
		x = X.front(), y = Y.front();
		X.pop(), Y.pop();
		for (int i = 0; i < 8; i++) {
			if (move(n, m, x, y, i, tx, ty)) {
				if (dist[tx][ty] > dist[x][y] + 1) {
					dist[tx][ty] = dist[x][y] + 1;
					X.push(tx), Y.push(ty);
				}
			}
		}
	}
	
	// record sssp
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			hdist[sx][sy][i][j] = dist[i][j];
		}
	}
}
#define MAXL (100>>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[5500], Pt = 0;
void sieve() {
	register int i, j, k;
	SET(1);
	int n = 100;
	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;
		}
	}
}
// IDA
int ida_depth, solved;
int used[16][16];
int IDA(int x, int y, int ex, int ey, int dep, int hv) {
    if (hv == 0) {
        if (!GET(dep)) {
        	solved = 1;
        	return dep;
        }
        return 0x3f3f3f3f;
        return dep;
    }
    if (dep + hv > ida_depth)
        return dep + hv;
    int back = 0x3f3f3f3f, shv, tmp;
    for (int i = 0; i < g[x][y].size(); i++) {
    	int tx = g[x][y][i].first, ty = g[x][y][i].second;
        shv = hdist[tx][ty][ex][ey];
        
        if (used[tx][ty])
        	continue;
        	
        used[tx][ty] = 1;
        tmp = IDA(tx, ty, ex, ey, dep + 1, shv);
        used[tx][ty] = 0;
        
        back = min(back, tmp);
        if (solved) return back;
    }
    return back;
}
int main() {
	sieve();
	int n, m, sx, sy, ex, ey;
	int cases = 0;
	while (scanf("%d %d %d %d %d %d", &n, &m, &sx, &sy, &ex, &ey) == 6) {
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				moveBfs(n, m, i, j);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				g[i][j].clear();
				for (int k = 0; k < 8; k++) {
					int tx, ty;
					if (move(n, m, i, j, k, tx, ty))
						g[i][j].push_back(make_pair(tx, ty));
				}
			}
		}
		
//		printf("Bfs %d\n", hdist[sx][sy][ex][ey]);
//		for (int i = 0; i < n; i++, puts(""))
//			for (int j = 0; j < m; j++)
//				printf("%d ", hdist[sx][sy][i][j] == 0x3f3f3f3f ? -1 : hdist[sx][sy][i][j]);
		
		printf("CASE# %d: ", ++cases);
		
		if (hdist[sx][sy][ex][ey] > 1 && hdist[sx][sy][ex][ey] < 100 && !GET(hdist[sx][sy][ex][ey])) {
			printf("The knight takes %d prime moves.\n", hdist[sx][sy][ex][ey]);
			continue;
		}
				
		solved = 0;
		if (hdist[sx][sy][ex][ey] != 0x3f3f3f3f && (sx != ex || sy != ey)) {
			memset(used, 0, sizeof(used)); 
			
			used[sx][sy] = 1;
			ida_depth = 0;
			for (int i = 0; i < Pt && P[i] < 11; i++) {
				if (P[i] < ida_depth)
					continue;
				ida_depth = P[i];
				ida_depth = IDA(sx, sy, ex, ey, 0, hdist[sx][sy][ex][ey]);
				
				if (solved) {
					printf("The knight takes %d prime moves.\n", P[i]);
					break;
				}
			}
		}
		if (!solved) {
			if (hdist[sx][sy][ex][ey] == 0x3f3f3f3f)
				printf("Destination is not reachable.\n");
			else
				printf("The knight takes %d composite move(s).\n", hdist[sx][sy][ex][ey]);
		}
	}
	return 0;
} 
/*
5 7 2 2 3 1
5 5 0 0 3 4
5 5 0 0 4 4
5 5 0 0 0 0
8 4 4 0 3 2
4 8 1 1 3 5
5 7 2 2 3 1
7 8 0 7 0 5
7 5 1 4 0 4
5 6 1 4 0 2
6 4 0 2 0 1
8 8 1 0 2 7
8 5 0 1 6 1
7 8 1 5 1 4
*/