題目連結: https://tioj.ck.tp.edu.tw/problems/1034
# 內容
米勒上尉收到一道緊急命令，要求將二等兵雷恩即刻護送至指定地點。米勒上尉馬上攤開戰場地圖，希望能規畫出一條最安全的路線。戰場地圖可視為一個 N×N 的表格，表格中的每個位置只可以往東、南、西、北四個鄰近的位置移動。根據情報，米勤上尉已經掌握每個位置的敵軍兵力，所謂最安全的路線，指的是這條路線上所有敵軍兵力總和最小的路線。米勒上尉可以用「一發」死光炸彈轟炸地圖上的「一個」位置，轟炸過後該位置的敵軍將灰飛湮滅，幫助米勒上尉找出在一發死光炸彈支援下，最安全路線的敵軍兵力總數。
# 思路
這題因為可以轟掉一格，所以用 DP 做不好做，仔細想想我們如果可以快速得到任意兩點的最短距離的話，那就直接枚舉炸掉所有位置，看看哪樣比較短就好了啊。式子就會轉換成 ans = min {dis [a][k] + dis [k][b]-val [k]} 這樣的話，用學過的 floyed-warshall 就好啦！
不過說直接 floyd-warshall 很容易，但本題給的是點權，可能沒辦法好好做，所以就要將輸入進來的數上下左右做出連結，而座標的話... 用 Hash 轉換一下就好啦
# 程式碼
#include <bits/stdc++.h> | |
using namespace std; | |
#define maxn 405 | |
int N, Q, x,y, x2, y2; | |
int val[maxn], dis[maxn][maxn], minn; | |
inline int Hash(int x, int y){ | |
return x * N + y; | |
} | |
int main() { | |
while(cin >> N){ | |
for (int i = 0; i < maxn; i++){ | |
for (int j = 0; j < maxn; j++){ | |
if (i == j) dis[i][j] = 0; | |
else dis[i][j] = 0x3FFFFFFF; | |
} | |
} | |
//transform | |
for (int i = 0; i < N; i++){ | |
for (int j = 0; j < N; j++){ | |
cin >> val[Hash(i, j)]; | |
if (i != 0){ | |
dis[Hash(i, j)][Hash(i-1, j)] = val[Hash(i-1, j)]; | |
dis[Hash(i-1, j)][Hash(i, j)] = val[Hash(i, j)]; | |
} | |
if (j != 0){ | |
dis[Hash(i, j)][Hash(i, j-1)] = val[Hash(i, j-1)]; | |
dis[Hash(i, j-1)][Hash(i, j)] = val[Hash(i, j)]; | |
} | |
} | |
} | |
//Floyd-Warshall | |
for (int i = 0; i < N*N; i++) | |
for (int j = 0; j < N*N; j++) | |
for (int k = 0; k < N*N; k++) | |
dis[j][k] = min(dis[j][k],dis[j][i] + dis[i][k]); | |
cin >> Q; | |
while (Q--){ | |
minn = 0x7FFFFFFF; | |
cin >>x>>y>>x2>>y2; | |
x--,y--,x2--,y2--; | |
for (int i = 0; i < N*N; i++) | |
minn = min(minn, val[Hash(x, y)] + dis[Hash(x, y)][i] + dis[i][Hash(x2, y2)] - val[i]); | |
cout << minn << "\n"; | |
} | |
} | |
} |
