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;
}
發佈留言