# 題目: 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/