# 題目: UVa 10653 - Bombs! NO they are Mines!!

# 題目說明

現在是 3002 年,機器人已經統治了世界,你是少數存活的人類之一
機器人一直用你來比對他們是否能變得更聰明
今天是一個特別的日子,只要你能在 IRQ2003 領域中擊敗最快的機器人,你就會獲得自由
就算他們是智能的,但機器人仍無法改變他們的基本缺陷:只能走 上 下 左 右
你擁有一張顯示不安全區域的地圖,你必須找到從起點到終點的最短路徑


INPUT:
每筆資料第一行有兩個整數 RC ,代表地圖的大小
第二行有一個整數 N ,代表以下有幾筆資料
接下來有 N 行,每行先讀入兩個整數 rk ,代表第幾行與炸彈數
接下來 k 個資料,讀入一個整數 c 代表炸彈位於 rc
RC0 時,結束程式


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/