TIOJ 1143 95_4.靈犬尋寶

作者:

題目連結：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();
    }
}

發佈留言