首次架設靜態網站，如有疏失，還請多多包涵。歡迎來信zhuastor@gmail.com

解題心得

這題就挺經典的走迷宮、尋寶藏的BFS題目，沒試過DFS但感覺會TLE(感覺…)
主要是前陣子讀到BFS的章節，有去了解它的核心觀念，剛好有學到象棋馬
所以我想起很久前在刷DFS題目的時候看到了這題
結果我吃了3個WA…，真的要看清題目，我直覺認為這就跟象棋馬一樣走個”日”…
這題因為會輸入好多筆測資，所以我使用的布林陣列就要回歸false，還有deque也要清空
然後才發現自己又忘記布林陣列能不能搭配memset了…嘿嘿

解題想法

這題我的解題關鍵是在判斷障礙和之後動作的整個過程，其他就是簡單的BFS模板(我這部分主要使用deque，不會去查一下，很好用)
我判斷靈犬能不能走那格的方法是，在每次探查新的點時，先檢查他上、下、左、右(jx、jy陣列)，如果非障礙物，再利用數字上的性質(事先操控)
轉到下一個真正要走的點(dx、dy陣列)，而此時迴圈的變數就是前面特意操控的jx、jy陣列的變數”乘於2”~”乘於2後加1”
這裡有點複雜，最好動手寫寫看，主要是事先準備好dx、dy陣列中的內容與jx、jy陣列中內容的關聯(當然這個非必要，只是解題的小技巧)
有些部分還請自己想想看，盡量不要用背的，例如dx、dy陣列的設立、此點經過還是沒有經過的各種判斷
如果是剛開始碰到BFS、DFS的初學者，不要忘記迷宮問題通常都會需要有結界的限制，記得檢查!

AC code

#include<bits/stdc++.h>
using namespace std;
struct job{
  int x,y;
  int step;
};
int dx[]={3,3,1,-1,-3,-3,1,-1};
int dy[]={1,-1,3,3,1,-1,-3,-3};
int mind=999999;
bool ta[105][105];
bool ta1[105][105];
int jx[]={1,0,-1,0};
int jy[]={0,1,0,-1};
deque<job>now;
int main(){
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int sx,sy;
  int gp,gk;
  int ex,ey;
  int n;
  job next,num;
  while(cin >> n){
    now.clear();
    memset(ta,0,sizeof(ta));
    memset(ta1,0,sizeof(ta1));
    mind=999999;
      for(int x=0;x<n;x++){
      cin >> gp >> gk;
      ta[gp][gk]=true;
    }
    cin >> sx >> sy;
    cin >> ex >> ey;
    next.x=sx;
    next.y=sy;
    next.step=0;
    ta1[sx][sy]=true;
    int kx,ky;
    now.push_back(next);
    bool ta2=false;
    while(!now.empty()){
      next=now.front();
      now.pop_front();
      for(int z=0;z<4;z++){
        if(ta2){
          break;
        }
        kx=next.x+jx[z];
        ky=next.y+jy[z];
        if(!ta[kx][ky] && (kx>=0 && kx<=99) && (ky>=0 && ky<=99)){
          for(int g=2*z;g<=(2*z)+1;g++){
            kx=next.x+dx[g];
            ky=next.y+dy[g];
            num.step=next.step+1;
            num.x=kx;
            num.y=ky;
            if(!ta[kx][ky] && !ta1[kx][ky] && (kx>=0 && kx<=99) && (ky>=0 && ky<=99) && (kx!=(ex) or ky!=(ey))){
              ta1[num.x][num.y]=true;
              now.push_back(num);
            }
            else if(!ta[kx][ky] && !ta1[kx][ky] && (kx>=0 && kx<=99) && (ky>=0 && ky<=99) && (kx==(ex) && ky==(ey))){
              mind=num.step;
              now.clear();
              ta2=true;
              break;
            }
          }
        }
      }
    }
    if(mind!=999999)
    cout << mind << endl;
    else{
      cout << "impossible" << endl;
    }
  }
  
  return 0;
}

題目連結 : 95年全國資訊學科能力競賽 4.靈犬尋寶