[UVA][TSP] 11643 - Knight Tour
Problem H
Knight Tour
Input: Standard Input
Output: Standard Output
In the game of chess in 8 x 8 grid a knight can move in an interesting way. Its moves are like “L” shape. A knight can move from cell (r1, c1) to cell (r2, c2) if and only if (r1 - r2)2 + (c1 - c2)2 = 5.
For this problem consider a grid of size N x N. There are K interesting cell in our grid. We have a knight which can start his journey from any cell it likes in the grid. His aim is to visit all interesting cells at least once and back to its initial position.
Your task is to calculate the minimum number of moves required for the knight to finish its journey.
Image: knight moves
Input
Input will start with an integer T(T≤100) which denotes the number of test cases. Each case starts with two integers N(4≤N≤1000) and K(1≤K≤16). Each of the next K lines contains two integers R(1≤R≤N) and C(1≤C≤N). Here (R, C) represents an interesting cell.
Output
Output one line for each test case. Print the case number followed by the number of minimum moves required.
Look at the sample input output for exact format.
Sample Input Output for Sample Input
|
1 8 3 2 3 4 5 6 7 |
Case 1: 12 |
題目最難的地方不在於 DP 的 TSP 處理。
在點數 n <= 16，TSP 也不過處理 O(16*16*2^16)=O(16777216)
而是預處理 TSP 的點與點之間的距離，由於要求騎士走訪，
又必須考慮邊界效應，在不同邊界下，相同座標組間的距離也會不一
邊界最大到 O(1000x1000)
建圖如果使用 O(16*1000*1000) 雖然差不多跟 16777216 差不多，
但是當 n 越來越小時，差別就會讓你 TLE。
如何使用假解估算出兩點距離？
預處理一個無限大的板子的 BFS，以及
最後是特別 case 兩點距離小於某定值進行搜索。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
int dist[1005][1005] = {};
int g[16][16];
void bfs() {
static int dx[] = {1,1,-1,-1,2,2,-2,-2};
static int dy[] = {2,-2,2,-2,1,-1,1,-1};
int i, j, k, x, y, tx, ty;
queue<int> X, Y;
X.push(0), Y.push(0);
while(!X.empty()) {
x = X.front(), X.pop();
y = Y.front(), Y.pop();
for(i = 0; i < 8; i++) {
tx = x+dx[i], ty = y+dy[i];
if(tx < 0 || ty < 0 || tx > 1000 || ty > 1000)
continue;
if(dist[tx][ty] == 0) {
dist[tx][ty] = dist[x][y]+1;
X.push(tx), Y.push(ty);
}
}
}
dist[0][0] = 0;
}
int dist2[1005][1005], used[1005][1005] = {};
int bfs2(int x1, int y1, int x2, int y2, int n) {
static int dx[] = {1,1,-1,-1,2,2,-2,-2};
static int dy[] = {2,-2,2,-2,1,-1,1,-1};
static int cases = 0;
++cases;
int i, j, k, x, y, tx, ty;
queue<int> X, Y;
X.push(x1), Y.push(y1);
dist2[x1][y1] = 0;
while(!X.empty()) {
x = X.front(), X.pop();
y = Y.front(), Y.pop();
if(dist2[x][y] > 30) break;
for(i = 0; i < 8; i++) {
tx = x+dx[i], ty = y+dy[i];
if(tx < 1 || ty < 1 || tx > n || ty > n)
continue;
if(used[tx][ty] != cases) {
used[tx][ty] = cases;
dist2[tx][ty] = dist2[x][y]+1;
if(tx == x2 && ty == y2)
return dist2[tx][ty];
X.push(tx), Y.push(ty);
}
}
}
return 0xfffff;
}
int dp[1<<16][16];
int dfs(int state, int last, int n) {
int &ret = dp[state][last];
if(ret != -1) return ret;
if(state == 0)
return g[last][0];
ret = 0xfffffff;
int i;
for(i = 0; i < n; i++) {
if((state>>i)&1) {
ret = min(ret, dfs(state^(1<<i), i, n)+g[last][i]);
}
}
return ret;
}
int main() {
bfs();
int testcase, cases = 0;
int n, m;
int x[16], y[16];
int i, j, k;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %d", &n, &m);
for(i = 0; i < m; i++)
scanf("%d %d", &x[i], &y[i]);
for(i = 0; i < m; i++) {
for(j = 0; j < m; j++) {
if(abs(x[i]-x[j])+abs(y[i]-y[j]) > 20)
g[i][j] = dist[abs(x[i]-x[j])][abs(y[i]-y[j])];
else
g[i][j] = bfs2(x[i], y[i], x[j], y[j], n);
}
g[i][i] = 0;
}
memset(dp, -1, sizeof(dp));
int ans = dfs((1<<m)-1-1, 0, m);
/*for(i = 0; i < m; i++, puts(""))
for(j = 0; j < m; j++)
printf("%4d ", g[i][j]);*/
printf("Case %d: %d\n", ++cases, ans);
}
return 0;
}