UVa10477 - The Hybrid Knight(BFS)

題目大意

生物學家讓西洋棋的騎士更跟其他棋子進行雜交，因此現在產生了一種棋子叫做怪異騎士，怪異騎士總共有三種型態，依序是普通騎士、變異騎士、變異士兵。

• 普通騎士與一般騎士走法相同
• 變異騎士則是比一般騎士的長度再多一格
• 變異士兵走法與一般士兵相同，但變異士兵在走最後一步時可以走一格對角線

現在給你一個棋盤 \(N*N\) 再給你怪異騎士的初始位置，請你讓怪異騎士走到終點。
請給出最小步數走法

題目連結

重點觀念

• 多種狀態在棋盤上行走時要如何解決
• BFS

分析

• 這邊的 BFS 與其他類似題目的 BFS 不同，由於他有不同形態，因此不可以單單只有 visit 來判斷此格子是否有經過。
  • 舉例：普通騎士走到 x 位置，變異騎士走到 y 位置，變異士兵走到 z 位置，普通騎士走到 a 位置，變異騎士走到 x 位置，此時，x 位置就有了變異騎士、普通騎士的走法。
  • 因此我們 visit 還要針對每一種不同的型態分開討論。
  • 因此我們這樣也不在使用 dist，因為這樣必須按照多種形態再去開創，較為麻煩
  • 比較簡單的辦法是將步數也直接存入 deque 裡面，就可以達到狀態延續。
  注意：這是因為題目只問最後一步才可以這樣做
• BFS 也必須按照型態順序不斷進行 BFS
• 紀錄，題目一開始沒有說初始點怪異騎士是甚麼型態，因此三種都要舉例
• 變異士兵的最後一步需要拉進來討論，但不需要再放入 deque 裡面

心得

真的很想罵髒話…，這題目有夠噁心 = =，可以把題目出成這樣真的太鬼了，我為了解這題花了 4hr，我還沒有覺得我學到了甚麼大觀念、大格局，只有學到一些小技巧，然後發現一些缺點，就重新編寫程式碼。

天啊，這快跟 poker code 一樣難過:(

可以看看我下面的 code，就知道我到底 debug 多少次XD。

參考連結

UVa 10477 by monir-bjit

題目程式碼

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

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
#define MAXN 25
#define INF 0x3f3f3f
using namespace std;
int kx[] = {-2, -2, -1, -1, 2, 2, 1, 1}; //普通騎士走法
int ky[] = {-1, 1, -2, 2, -1, 1, -2, 2};
int mx[] = {-3, -3, -1, -1, 3, 3, 1, 1}; //變異騎士走法
int my[] = {1, -1, -3, 3, -1, 1, -3, 3};
int px[] = {0, 0, -1, 1}; //變異小兵普通走法
int py[] = {-1, 1, 0, 0};
int dx[] = {1, 1, -1, -1}; //變異小兵最後一步走法
int dy[] = {-1, 1, -1, 1};

int visit[3][MAXN][MAXN]; //記錄各種狀態在此格子是否有走過
int n, s, b, e, kase=0, cmd, cost; 
int bx, by, ex, ey; //b 起點 e 終點
int x, y, m, tx, ty;

struct node{
    int x, y, m, cost; //x,y 座標 m 現在是哪個型態, cost 從一開始到現在已經走了幾步
    node(): x(0), y(0), m(0), cost(0) {}
    node(int x, int y, int m, int cost): x(x), y(y), m(m), cost(cost) {}
};
deque<node> q;

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

void pushK(){ //普通騎士走法
    for(int i = 0; i < 8; i++){
        tx = x + kx[i];
        ty = y + ky[i];
        if(isboard(tx,ty) && !visit[cmd][tx][ty]){
            visit[cmd][tx][ty] = 1;
            q.push_back({tx,ty,m+1, cost+1});
            //cout << "K tx ty cost " << tx << " " << ty << " " << cost+1 << "\n";
        }
    }
}

void pushM(){ //變異騎士走法
    for(int i = 0; i < 8; i++){
        tx = x + mx[i];
        ty = y + my[i];
        if(isboard(tx,ty) && !visit[cmd][tx][ty]){
            visit[cmd][tx][ty] = 1;
            q.push_back({tx,ty,m+1, cost+1});
            //cout << "M tx ty cost " << tx << " " << ty << " " << cost+1 << "\n";
        }
    }
}

void pushP(){ //變異小兵走法
    for(int i = 0; i < 4; i++){
        tx = x + px[i];
        ty = y + py[i];
        if(isboard(tx,ty) && !visit[cmd][tx][ty]){
            visit[cmd][tx][ty] = 1;
            q.push_back({tx,ty,m+1, cost+1});
            //cout << "P tx ty cost " << tx << " " << ty << " " << cost+1 << "\n";
        }
    }
}

void pushD(){ //變異小兵對角線走法
    for(int i = 0; i < 4; i++){
        tx = x + dx[i];
        ty = y + dy[i];
        if(isboard(tx,ty)){
            if(tx == ex && ty == ey){ //不需要 q.push_back() 因為不能再走
                visit[cmd][tx][ty] = 1;
                //cout << "D tx ty dist " << tx << " " << ty << " " << dist[tx][ty] << "\n";
            }
        }
    }
}

int spfa(){
    memset(dist, 0, sizeof(dist));
    memset(visit, 0, sizeof(visit));

    //各種狀態初始化
    q.push_back({bx, by, 0, 0});
    visit[0][bx][by] = 1;
    q.push_back({bx, by, 1, 0});
    visit[1][bx][by] = 1;
    q.push_back({bx, by, 2, 0});
    visit[2][bx][by] = 1;
    //cout << bx << " " << by << "\n";
    while(!q.empty()){
        x = q.front().x;
        y = q.front().y;
        m = q.front().m;
        cost = q.front().cost;
        q.pop_front();
        cmd = m % 3; //由於只有三種型態，因此 %3

        if(cmd == 0) pushK();
        if(visit[cmd][ex][ey]) return cost+1; //如果在這次普通騎士中有找到，表示再走一步就到，因此直接 return cost+1
        if(cmd == 1) pushM();
        if(visit[cmd][ex][ey]) return cost+1; //遇上面概念相同
        if(cmd == 2) pushP();
        if(visit[cmd][ex][ey]) return cost+1; //遇上面概念相同
        if(cmd == 2) pushD();
        if(visit[cmd][ex][ey]) return cost+1; //遇上面概念相同

    }
    return -1; //找不到，輸出 -1
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    while(cin >> n >> s && (n != 0)){
        cout << "Set " << ++kase << ":\n";
        for(int i = 0; i < s; i++){
            cin >> b >> e; //由於題目給一維陣列表達，我們直接將資料全部 -1，就可用一般數學比達
            //因此此題目中所有關於棋盤的 index 都從 0 開始
            b--; e--; 
            bx = b / n; by = b % n; //轉換成 x,y 座標
            ex = e / n; ey = e % n; //轉換成 x,y 座標
            q.clear();
            cout << spfa() << "\n"; //計算答案
        }

    }
    return 0;
}