2011-08-24 21:21:00Morris
d598. 3. 尋寶問題 (粗糙濫造版本)
d598. 3. 尋寶問題
內容 ：
問題敘述
星光遊樂園擁有全球最大的自動迷宮，迷宮內有 m 個可能的藏寶點，但每次重
新設定迷宮時最多只有 n 個藏寶點藏有寶物，且迷宮的路徑也可以做改變。尋
寶者如果在一定的時間內找到所有的寶物才能兌換與寶物等值的園區消費卷。消
費卷兌換額與尋找寶物過程中所走過的路徑距離成反比。換句話說，走過的路徑
距離越短，找到所有寶物後，所能換得的消費卷額就越高。為了確保園區營運正
常，發出去的消費卷必須有所拿捏。因此經營者希望能夠在每次迷宮設定好後，
自動算出從迷宮入口出發，找到所有寶物，最後至迷宮出口所需的最短路徑距
離，好依此數據設定消費卷兌換的準則。請寫一程式來計算此最短路徑距離。
條件說明
1. 迷宮內的可能藏寶點數 m, 2 ≤ m ≤ 20。可能藏寶點的代號為 1, 2, 3, …,
n。迷宮起始點代號為 1，迷宮出口點代號為 m。
2. 迷宮內的實際藏寶數為 n, 2 ≤ n ≤ 15。
3. 迷宮內的點對點路徑距離最短為 1，最長為 10。
星光遊樂園擁有全球最大的自動迷宮，迷宮內有 m 個可能的藏寶點，但每次重
新設定迷宮時最多只有 n 個藏寶點藏有寶物，且迷宮的路徑也可以做改變。尋
寶者如果在一定的時間內找到所有的寶物才能兌換與寶物等值的園區消費卷。消
費卷兌換額與尋找寶物過程中所走過的路徑距離成反比。換句話說，走過的路徑
距離越短，找到所有寶物後，所能換得的消費卷額就越高。為了確保園區營運正
常，發出去的消費卷必須有所拿捏。因此經營者希望能夠在每次迷宮設定好後，
自動算出從迷宮入口出發，找到所有寶物，最後至迷宮出口所需的最短路徑距
離，好依此數據設定消費卷兌換的準則。請寫一程式來計算此最短路徑距離。
條件說明
1. 迷宮內的可能藏寶點數 m, 2 ≤ m ≤ 20。可能藏寶點的代號為 1, 2, 3, …,
n。迷宮起始點代號為 1，迷宮出口點代號為 m。
2. 迷宮內的實際藏寶數為 n, 2 ≤ n ≤ 15。
3. 迷宮內的點對點路徑距離最短為 1，最長為 10。
輸入說明
：
第一行有兩個整數 m, n，分別代表可能藏寶位置數及實際藏寶數。第二行有 n
個整數，分別代表實際藏寶點的代號。接下來的 m 行（第3 行至第3+(m-1)行）
記錄該迷宮路徑的資訊：每一行都有 m 個整數，整數之間以一個空白隔開；第 i
行的第 j 個整數代表可能藏寶點 i 到可能藏寶點 j 的距離（與 j 到 i 的距
離相同）。若兩個可能藏寶點之間沒有直接相連的路徑，則以 0 代表之。任一可
能藏寶點到自己的距離也是 0。
個整數，分別代表實際藏寶點的代號。接下來的 m 行（第3 行至第3+(m-1)行）
記錄該迷宮路徑的資訊：每一行都有 m 個整數，整數之間以一個空白隔開；第 i
行的第 j 個整數代表可能藏寶點 i 到可能藏寶點 j 的距離（與 j 到 i 的距
離相同）。若兩個可能藏寶點之間沒有直接相連的路徑，則以 0 代表之。任一可
能藏寶點到自己的距離也是 0。
輸出說明
：
請輸出一整數，即從迷宮入口出發，找到所有寶物，最後至迷宮出口所需的最短路徑距離。
範例輸入
：
輸入範例 1 6 3 2 3 6 0 1 2 4 0 0 1 0 0 0 7 0 2 0 0 0 0 0 4 0 0 0 2 5 0 7 0 2 0 4 0 0 0 5 4 0 輸入範例 2 4 2 1 2 0 5 1 4 5 0 2 5 1 2 0 1 4 5 1 0
範例輸出 ：
輸出範例 1 15 輸出範例 2 6
提示
：
輸入範例 1 說明:
共有5 個藏寶點，其中3 個藏有寶物
藏寶點 2, 3, 6 藏有寶物，如下圖
輸入範例 2 說明
共有4 個藏寶點，其中2 個藏有寶物
藏寶點 1, 2 藏有寶物，如下圖
輸出範例 1 說明
路徑可為 1 2 1 3 1 4 6 或 1 3 1 2 1 4 6
輸出範例 2
說明
路徑為 1 3 2 3 4
出處
：
加了一堆啟發式的剪枝
/**********************************************************************************/
/* Problem: d598 "3. 尋寶問題" from 98全國賽 */
/* Language: C */
/* Result: AC (187ms, 224KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-24 20:31:44 */
/**********************************************************************************/
#include<stdio.h>
#include<string.h>
#define oo 40000
int Trea[21], n, m;
int map[21][21], Ans, F[21][21];
int next[21];
void Floyd() {
int a, b, c;
for(a = 1; a <= n; a++) {
for(b = 1; b <= n; b++) {
F[a][b] = map[a][b];
if(F[a][b] == 0) F[a][b] = oo;
if(a == b) F[a][b] = 0;
}
}
for(a = 1; a <= n; a++)
for(b = 1; b <= n; b++)
for(c = 1; c <= n; c++)
if(F[b][a]+F[a][c] < F[b][c])
F[b][c] = F[b][a]+F[a][c];
}
int H(int now) {
return F[now][n];
}
void DFS(int now, int find, int L) {
if(find == m) {
if(L+H(now) < Ans) Ans = L+H(now);
return;
}
if(L+H(now)+(m-find-1) >= Ans) return;
int a, pre = 0;
for(a = next[0]; a; pre = a, a = next[a]) {
if(F[now][Trea[a]]) {
next[pre] = next[a];
DFS(Trea[a], find+1, L+F[now][Trea[a]]);
next[pre] = a;
}
}
}
main() {
while(scanf("%d %d", &n, &m) == 2) {
memset(Trea, 0, sizeof(Trea));
int a, b, find = 0, x;
for(a = 1; a <= m; a++)
scanf("%d", &Trea[a]);
for(a = 0; a < m; a++)
next[a] = a+1;
next[m] = 0;
for(a = 1; a <= n; a++)
for(b = 1; b <= n; b++)
scanf("%d", &map[a][b]);
Floyd();
if(Trea[1] == 1) find++, next[0] = next[1];
Ans = oo, DFS(1, find, 0);
printf("%d\n", Ans);
}
return 0;
}
事實上是有 DP, 可以做的,
我自己想的, 不是到對不對,
用二進制紀錄是否有走過, 0 沒有 1 有走,
再多一個狀態紀錄最後走過的點,
(01010...0100) (last)
一直加點更新, 每次抓最小的出來,
直接抓到一個狀態是
(1111...1111) 結束迴圈