UVa10426 - Knights’ Nightmare(BFS)

題目大意

這個國家的人民們都是西洋棋騎士，因此他們只能夠走西洋棋棋法；土地也跟西洋棋的棋盤相似。
有天，他們的土地上出現了一個怪物，這個怪物很特別

• 長年都在睡覺
• 只要有一個騎士經過，怪物則會醒來，但不會吃掉他
• 接下來只要有其他騎士走過都會被吃掉

由於四位騎士必須聚在一起討論會議，因此他們要找一個沒有怪物的格子開會。
保險起見，當有一個騎士在行走時，其他騎士不會行走，以確保安全。
想知道，這些騎士們聚集在土地上的哪一個格子會讓騎士們行走距離最小，輸出最小行走距離。

題目連結

重點觀念

• BFS 應用

分析

• 首先我們針對四位騎士先執行允許經過怪物格子的 BFS
• 再來我們針對四位騎士執行不經過怪物格子的 BFS
• 再來我們先計算 四位騎士執行不經過怪物格子的 BFS 總和
• 然後針對 max(騎士允許經過怪物格子 - 騎士不允許經過怪物格子)，並將上一點的總和減去此公式就可算出答案
  • 因為題目說明可以讓一位騎士經過，因此我們有一個騎士經過怪物格子可以比不經過怪物格子還快，那我們就讓他抄近路。
  • 如果有多位騎士符合上一點條件，那就找最大的。
• 之後對每一個點都求出最小距離，最後再找出哪個點距離最小，輸出距離即可。

參考連結

UVa 10426 Knights’ Nightmare by morris
西洋棋走法 by 師大演算法筆記

心得

真的好討厭寫棋盤，每一次都寫得頭暈腦脹…。
棋盤真的好難搞 :(。

還有 memset(visit, 0, sizeof(visit[i])) 這樣會永遠只讓 visit[0] 被清空，一直被這個 bug 氣到:(

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
#define MAXN 20
using namespace std;
int dx[] = {1, 2, -1, -2, -2, -1, 1, 2}; //騎士方向
int dy[] = {2, 1, 2, 1, -1, -2, -2, -1};

string s;
int r, c;
//dist 不經過怪物格子、dist2 經過怪物格子
int dist[4][MAXN][MAXN], dist2[4][MAXN][MAXN]; 
int visit[4][MAXN][MAXN], visit2[4][MAXN][MAXN]; //判斷此路徑是否有走過
vector<pair<int,int> > people;
int mx, my; //monster x, y
int a, b;

int isboard(int x, int y){ //判斷是否在棋盤內
    if(x > 0 && x <= r && y > 0 && y <= c ) return 1;
    return 0;
}

// https://stackoverflow.com/questions/8767166/passing-a-2d-array-to-a-c-function
void spfa(int root_x, int root_y, int dist[MAXN][MAXN], int visit[MAXN][MAXN], int is_monster){ 
    deque<pair<int, int> > q;
    q.push_back({root_x, root_y});
    visit[q.front().first][q.front().second] = 1;
    if(is_monster == 1) visit[mx][my] = 1; //判斷這次的 spfa 是否有怪物

    int x, y, tx, ty;
    while(!q.empty()){
        x = q.front().first; 
        y = q.front().second;

        q.pop_front();
        for(int i = 0; i < 8; i++){
            tx = x + dx[i];
            ty = y + dy[i];
            if(isboard(tx,ty) && !visit[tx][ty]){ //判斷是否在棋盤內 && 沒有經歷過
                dist[tx][ty] = dist[x][y] + 1;
                //cout << "dist[tx][ty] " << dist[tx][ty] << "\n";
                visit[tx][ty] = 1; 
                q.push_back({tx,ty}); 
            }
        }
    }

}

int distance(int x, int y){
    //由於怪物在我們前面的 spfa 是被我們設定成一開始就被經歷過，所以這邊額外判斷
    if(x == mx && y == my) return 0x3f3f3f; 
    int cost = 0, reduce = 0;
    for(int i = 0; i < 4; i++){
        //沒被經歷過，表示無法抵達，直接回傳 INF
        if(dist2[i][x][y] == 0 && !visit2[i][x][y]) return 0x3f3f3f; 
        cost += dist2[i][x][y];
    }

    for(int i = 0; i < 4; i++){ //判斷經過怪物的走法會不會比較好
        if(dist[i][x][y] == 0 && !visit[i][x][y]) continue; //無法抵達，不用判斷
        reduce = max(dist2[i][x][y] - dist[i][x][y], reduce);
    }
    //cout << "x y cost reduce " << x << " " << y << " " << cost << " " << reduce << "\n";
    return cost - reduce;
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    while(cin >> s){
        cin >> r >> c;
        people.clear();
        for(int i = 0; i < 4; i++){
            cin >> a >> b;
            people.push_back({a,b});
        }
        cin >> mx >> my;

        memset(dist, 0, sizeof(dist));
        memset(dist2, 0, sizeof(dist2));
        memset(visit, 0, sizeof(visit));
        memset(visit2, 0, sizeof(visit2));
        for(int i = 0; i < 4; i++){ //輸入騎士座標
            spfa(people[i].first, people[i].second, dist[i], visit[i], 0);
            spfa(people[i].first, people[i].second, dist2[i], visit2[i], 1);

            /*
            cout << "debug dist2 \n";
            for(int j = 1; j <= r; j++){
                for(int k = 1; k <= c; k++)
                    cout << dist2[i][j][k] << " ";
                cout << "\n";
            }
            cout << "debug dist\n";
            for(int j = 1; j <= r; j++){
                for(int k = 1; k <= c; k++)
                    cout << dist[i][j][k] << " ";
                cout << "\n";
            }
            */
        }

        //對每一個點都求出最小距離，最後再找出哪個點距離最小，輸出距離即可。
        int ans = 0x3f3f3f;
        for(int i = 1; i <= r; i++){
            for(int j = 1; j <= c; j++){
                ans = min(ans, distance(i, j));
            }
        }

        cout << s << "\n";
        if(ans == 0x3f3f3f) cout << "Meeting is impossible.\n";
        else cout << "Minimum time required is " << ans << " minutes.\n";
    }
    return 0;
}