PF-象棋馬的移動

2022.11.07 PM 05:20 by CBJ

來源 : https://drive.google.com/file/d/1CMnis82zw9hGQHW1pRv3LFXACoUGA90Y/view
出題者 : 108資訊學科能力競賽複賽-彰雲嘉
標籤 : 枚舉、BFS(廣度優先搜尋)
難易度 : 4
解題想法 : 從起點開始BFS,只要一碰到終點必為最短路徑。
BFS參考 : https://alrightchiu.github.io/SecondRound/graph-breadth-first-searchbfsguang-du-you-xian-sou-xun.html#bfs
//C++ language
//solution link(含註解): https://github.com/CBJ0519/CBJsProgramDiary.com/blob/main/%E8%B3%87%E8%A8%8A%E5%AD%B8%E7%A7%91%E8%83%BD%E5%8A%9B%E7%AB%B6%E8%B3%BD/108%E5%BD%B0%E9%9B%B2%E5%98%89/PF-%E8%B1%A1%E6%A3%8B%E9%A6%AC%E7%9A%84%E7%A7%BB%E5%8B%95.cpp

#include<iostream>
#include<utility>
#include<queue>
#include<tuple>
#include<map>
using namespace std;
pair<int,int>target;
int X,Y;
bool inrange(int x,int y){
    return x>=0 && x<X && y>=0 && y<Y;
}
int dir[8][2]={{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}};
int bfs(int x,int y){
    queue<tuple<int,int,int>>q;
    q.push({x,y,0});
    map<pair<int,int>,bool>visited;
    while(!q.empty()){
        x=get<0>(q.front());
        y=get<1>(q.front());
        int step=get<2>(q.front());
        if(make_pair(x,y)==target)return step;
        q.pop();
        for(auto i:dir){
            int newx=x+i[0],newy=y+i[1];
            if(inrange(newx,newy) && !visited[{newx,newy}]){
                q.push({newx,newy,step+1});
                visited[{newx,newy}]=true;
            }
        }
    }
    return -1;
}
int main(){
    int n;cin>>n;
    while(n--){
        int a,b,c,d;
        cin>>X>>Y>>a>>b>>c>>d;
        target={c,d};
        cout<<bfs(a,b)<<"\n";
    }
    return 0;
}

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *