# 題目: UVa 10653 - Bombs! NO they are Mines!!
# 題目說明
現在是 3002 年,機器人已經統治了世界,你是少數存活的人類之一
機器人一直用你來比對他們是否能變得更聰明
今天是一個特別的日子,只要你能在 IRQ2003 領域中擊敗最快的機器人,你就會獲得自由
就算他們是智能的,但機器人仍無法改變他們的基本缺陷:只能走 上 下 左 右
你擁有一張顯示不安全區域的地圖,你必須找到從起點到終點的最短路徑
INPUT:
每筆資料第一行有兩個整數 R
和 C
,代表地圖的大小
第二行有一個整數 N
,代表以下有幾筆資料
接下來有 N
行,每行先讀入兩個整數 r
和 k
,代表第幾行與炸彈數
接下來 k
個資料,讀入一個整數 c
代表炸彈位於 r
行 c
排
當 R
和 C
為 0
時,結束程式
OUTPUT:
輸出起點到終點最短路徑的步數
# 解題方法
先建圖,將炸彈標至圖上 -1
接著進行 bfs,將每次走過的步數紀錄,當現在的位置 = 終點時結束
# 參考程式碼
#include <iostream> | |
#include <vector> | |
#include <memory.h> | |
#include <queue> | |
using namespace std; | |
const int nxt[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} }; | |
int M[1002][1002]; | |
int R, C; | |
int x_1, y_1, x_2, y_2; | |
int bfs() | |
{ | |
queue< pair<int, int> > Q; | |
Q.push({ x_1, y_1 }); | |
M[x_1][y_1] = 1; | |
while (!Q.empty()) | |
{ | |
auto [ux, uy] = Q.front(); | |
Q.pop(); | |
for (int i = 0; i < 4; ++i) | |
{ | |
int vx = ux + nxt[i][0]; | |
int vy = uy + nxt[i][1]; | |
if (vx >= 0 && vy >= 0 && vx < R && vy < C && !M[vx][vy]) | |
{ | |
M[vx][vy] = M[ux][uy] + 1; | |
if (vx == x_2 && vy == y_2) return M[vx][vy] - 1; | |
Q.push({ vx, vy }); | |
} | |
} | |
} | |
return -1; | |
} | |
int main() | |
{ | |
// fast io | |
ios::sync_with_stdio(false); | |
cin.tie(nullptr); | |
cout.tie(nullptr); | |
int N, r, k, c; | |
while (cin >> R >> C, R && C) | |
{ | |
memset(M, 0, sizeof(M)); | |
// build map | |
cin >> N; | |
while (N--) | |
{ | |
cin >> r >> k; | |
while (k--) | |
{ | |
cin >> c; | |
M[r][c] = 1; | |
} | |
} | |
cin >> x_1 >> y_1 >> x_2 >> y_2; | |
cout << bfs() << "\n"; | |
} | |
return 0; | |
} |
# 參考資料
https://blog.csdn.net/mobius_strip/article/details/21484637
http://naivered.github.io/2018/03/08/Problem_Solving/UVa/UVa-10653-Bombs-NO-they-are-Mines/