題目連結:1143 – 4.靈犬尋寶 | TIOJ INFOR Online Judge
題目敘述 :
正方形(左下角座標為(0,0),右上角座標為(99,99))的格網上,有一隻靈犬要尋找一個寶物,格網上除了靈犬與寶物之外,還有一些障礙物。一般情況下,只要不超出格網的邊界,靈犬的每一步最多有8個方向可供選擇,如圖一;但是必須注意,只有在A點沒有障礙物時才可以選擇方向1或方向2,只有在B點沒有障礙物時才可以選擇方向3或方向4,只有在C點沒有障礙物時才可以選擇方向5或方向6,只有在D點沒有障礙物時才可以選擇方向7或方向8。如果靈犬可以從出發的位置走到寶物的位置,其總共使用的步數,理論上應有一個最小值;但是靈犬也有可能無法走到寶物的位置。過程中,靈犬不可以走到障礙物的位置上。
以圖二為例,有多達4個障礙物介於靈犬與寶物之間,但是靈犬最快只要2步就可以到達寶物的位置。圖三是另一個例子,靈犬的位置靠近角落,雖然只有2個障礙物,靈犬卻無法到達寶物的位置。
請撰寫一個程式,若靈犬可以從最初位置走到寶物的位置時,請列印出其使用之最少步數;若靈犬無法到達寶物的位置,請列印出單字『impossible』。
輸入說明 :
第一行為一個整數n,代表障礙物的個數,0 ≤ n ≤ 1000。接下來的n行,每行表示一個障礙物的座標,其橫座標值與縱座標值間以一個空白隔開。 再下來的一行,表示靈犬的最初位置,其橫座標值與縱座標值間以一個空白隔開。 最後一行,代表寶物的位置,其橫座標值與縱座標值間以一個空白隔開。 注意:輸入之障礙物、靈犬、寶物皆在不同位置。所有橫、縱座標值均為介於0(含)至99(含)之間的整數。
輸出說明 :
依行走之規則,若靈犬可以從其位置走到寶物的位置時,請列印出其使用之最少步數;若靈犬無法到達寶物的位置,請列印出單字『impossible』。
範例輸入 1 :
4
3 6
4 5
5 4
6 3
3 3
7 5
範例輸出 1 :
2
範例輸入 2 :
2
1 1
0 2
0 1
4 3
範例輸出 2 :
impossible
題解 :
這很明顯是圖的BFS,而為何不是DFS呢?因為題目要求輸出最短的路徑,而在DFS的時候,只要下一步能走就一直走,因此不一定會是最短路徑。
在BFS時,要先判斷座標是否存在,再看是否會被阻擋,以及是否已經到過,最後還有目標位置有無障礙物。若以上條件均通過才能將他推入佇列。
實作程式碼如下
#include<bits/stdc++.h>
using namespace std;
//這樣在宣告long long 時可以用ll代替
using ll=long long;
//常數N表示最大地圖長寬,多5以求保險
const ll N=105;
//位置
struct Pos{
int r,c;
friend bool operator==(Pos a,Pos b){
return (a.r==b.r && a.c==b.c);
}
void operator+=(Pos b){
r+=b.r;
c+=b.c;
}
};
//位置變化量
struct Deg{
Pos pos;
Pos lmt;
};
const Deg d[8]={
{Pos{ 3, 1},Pos{ 1, 0}},
{Pos{ 3,-1},Pos{ 1, 0}},
{Pos{ 1,-3},Pos{ 0,-1}},
{Pos{-1,-3},Pos{ 0,-1}},
{Pos{-3, 1},Pos{-1, 0}},
{Pos{-3,-1},Pos{-1, 0}},
{Pos{-1, 3},Pos{ 0, 1}},
{Pos{ 1, 3},Pos{ 0, 1}}
};
int n;
void solve(){
// mp存那些位置有障礙物
bitset<N> mp[N];
int ct[N][N]={0};
for(int i=0;i<n;++i){
int r,c;
cin>>r>>c;
mp[r][c]=true;
}
Pos pos,loot;
cin>>pos.r>>pos.c;
cin>>loot.r>>loot.c;
if((abs(pos.r-loot.r)+abs(pos.c-loot.c)) & 1){
cout<<"impossible"<<"\n";
return;
}
bool isf=false;
// 初始化
queue<Pos> bfs;
bfs.push(pos);
// 用1初始化避免以為沒到過
ct[pos.r][pos.c]=1;
while(!bfs.empty()){
Pos now=bfs.front();
bfs.pop();
if(now==loot){
// 因為初始化為1,因此就要將答案-1
cout<<ct[now.r][now.c]-1<<"\n";
isf=true;
break;
}
for(int i=0;i<8;++i){
Pos next=now;
next+=d[i].pos;
// 座標存在與否
if(next.r<100 && next.c<100 && next.r>=0 && next.c>=0){
// 目標位置有無障礙物
if(!mp[next.r][next.c]){
// 是否會被阻擋
if(!mp[now.r+d[i].lmt.r][now.c+d[i].lmt.c]){
// 是否已經到過
if(!ct[next.r][next.c]){
bfs.push(next);
ct[next.r][next.c]=ct[now.r][now.c]+1;
}
}
}
}
}
}
if(!isf){
cout<<"impossible"<<"\n";
}
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
//處理多筆輸入(用於ZeroJudge:b059),但單筆輸入也不會錯
while(cin>>n){
solve();
}
}