看了網絡上其他人的代碼,才明白怎麼做。
先用BFS算出,每個點到其他點間的距離,即每個財寶之間的最短路(包括起點),然後狀壓最短路處理。
具體做法:
狀態壓縮,1表示當前的財寶已經得到,0表示當前的財寶還未得到。
dp[st][i] 表示當前已經得到財寶為st 的情況下的終點為i 。
那麼枚舉下一次要到達的點 j。
得出狀態轉移公式為:
dp[st|(1<
有兩種情況起點為負數,財寶之間不能聯通,這兩種情況要輸出-1;存在一個財寶且財寶在原點,這種情況要輸出0。
AC代碼
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 105;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = { 0,-1, 0, 1};
struct Point {
int x, y;
Point() {}
Point(int _x, int _y) {
x = _x, y = _y;
}
}poi[20];
struct Node {
int x, y, dist;
Node() {}
Node(int _x, int _y, int _dist) {
x = _x; y = _y; dist = _dist;
}
};
int grid[N][N], dist[20][20], dp[(1<<12)][20];
int n, m, tot;
bool vis[N][N];
int bfs(int star, int end) {
memset(vis, false, sizeof(vis));
queue que;
que.push(Node(poi[star].x, poi[star].y, 0));
int step, x, y;
while(!que.empty()) {
Node front = que.front();
que.pop();
if(front.x == poi[end].x && front.y == poi[end].y)
return front.dist;
for(int i = 0; i < 4; i++) {
x = front.x + dx[i];
y = front.y + dy[i];
if(x < 1 || x > n || y < 1 || y > m || grid[x][y] < 0) continue;
if(!vis[x][y]) {
vis[x][y] = true;
step = front.dist + 1;
que.push(Node(x, y, step));
}
}
}
return -1;
}
bool getDist() {
memset(dist, 0, sizeof(dist));
for(int i = 0; i <= tot; i++) {
for(int j = 0; j < i; j++) {
dist[i][j] = dist[j][i] = bfs(i, j);
if(dist[i][j] == -1) return false;
}
}
return true;
}
int tsp() {
memset(dp,INF,sizeof(dp));
dp[1][0] = 0;
int end = (1<<(tot+1)) - 1;
for (int st=0; st <=end; st++)
for(int i=0; i <= tot; i++)
for(int j=0;j <= tot; j++) {
if (i == j) continue;
if ((1 << i) & st == 0 || (1 << j) & st == 1) continue;
if (dp[st][i] == INF) continue;
dp[st|(1< 0)
poi[++tot] = Point(i, j);
}
}
if(tot == 0) {
puts("0");
continue;
}
poi[0] = Point(1, 1);
if(grid[1][1] < 0 || !getDist()) {
puts("-1");
continue;
}
printf("%d\n", tsp());
}
return 0;
}