【題目敘述】https://tioj.ck.tp.edu.tw/problems/1034
【解題想法】使用Floyd-Warshall計算最短路徑。
- 輸入測資為二維矩陣，先將其轉換為一維陣列儲存，方便後續計算點對點的距離。
- 初始值：起點終點相同時設為 0，其餘設為INF（0x3FFFFFFF，避免加法運算時可能overflow）。
- 因為每個位置只可以往東、南、西、北四個鄰近的位置移動，讀入測資時順便計算點到點的敵軍兵力（不含起點）。
- 利用標準Floyd-Warshall演算法，計算全點對最短路徑。
- 枚舉「一發」死光炸彈轟炸位置，計算起點終點間最安全路線的敵軍兵力總數（計入起點的兵力，及扣除死光炸彈轟炸位置的兵力）。
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
#define maxn 405
int N, Q, x1, y1, x2, y2;
int a[maxn], ans[maxn][maxn], mn;
int f(int x, int y){
// 將二維的陣列index換算成一維index
return x * N + y;
}
int main() {
while(cin >> N){
// 初始值：起點終點相同時設為 0，其餘設為INF
// 因為後續有加法運算，因此INF = 0x3FFFFFFF
for (int i = 0; i < maxn; i++){
for (int j = 0; j < maxn; j++){
if (i == j) ans[i][j] = 0;
else ans[i][j] = 0x3FFFFFFF;
}
}
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
// 讀入測資時，同時將二維資料轉存成一維陣列
cin >> a[f(i, j)];
// 趁著讀入測資時，判斷移動後會不會超出邊界，
// 計算相鄰點到點的敵軍兵力(不含起點)
if (i != 0){
// 東西向移動
ans[f(i, j)][f(i-1, j)] = a[f(i-1, j)];
ans[f(i-1, j)][f(i, j)] = a[f(i, j)];
}
if (j != 0){
// 南北向移動
ans[f(i, j)][f(i, j-1)] = a[f(i, j-1)];
ans[f(i, j-1)][f(i, j)] = a[f(i, j)];
}
}
}
// 標準Floyd-Warshall做法
// i：枚舉中間點
// j, k：計算all-pairs shortest path
for (int i = 0; i < N*N; i++){
for (int j = 0; j < N*N; j++){
for (int k = 0; k < N*N; k++){
if (ans[j][k] > ans[j][i] + ans[i][k]){
ans[j][k] = ans[j][i] + ans[i][k];
}
}
}
}
// 輸入起點終點，計算最安全路線的敵軍兵力總數
cin >> Q;
while (Q--){
mn = 0x7FFFFFFF;
cin >> x1 >> y1 >> x2 >> y2;
// 座標值轉成zero-based
x1--;
y1--;
x2--;
y2--;
// i：枚舉「一發」死光炸彈轟炸位置
for (int i = 0; i < N*N; i++){
// 計入起點兵力：a[f(x1, y1)]
// 扣除死光炸彈轟炸位置的兵力：a[i]
mn = min(mn, a[f(x1, y1)] + ans[f(x1, y1)][i] + ans[i][f(x2, y2)] - a[i]);
}
cout << mn << "\n";
}
}
}