＜藍橋杯＞DFS深度優先搜尋習題總結

1. 中國象棋

題目描述

中國象棋博大精深，其中馬的規則最為複雜，也是最難操控的一顆棋子。我們都知道象棋中馬走"日"，比如在 (2,4)(2, 4)(2,4) 位置的一個馬，跳一步能到達的位置有 (0,3)(0, 3)(0,3)，(0,5)(0, 5)(0,5)，(1,2)(1, 2)(1,2)，(1,6)(1, 6)(1,6)，(3,2)(3, 2)(3,2)，(3,6)(3, 6)(3,6)，(4,3)(4, 3)(4,3)，(4,5)(4, 5)(4,5)。

蒜頭君正在和花椰妹下棋，蒜頭君正在進行戰略布局，他需要把在 (x,y)(x,y)(x,y) 位置的馬跳到 (x′,y′)(x’, y’)(x′,y′) 位置，以達到威懾的目的。但是棋盤大小有限制，棋盤是一個 10×9 的網格，左上角坐标為 (0,0)(0, 0)(0,0)，右下角坐标為 (9,8)(9, 8)(9,8)，馬不能走出棋盤，并且有些地方已經有了棋子，馬也不能跳到有棋子的點。蒜頭君想知道，在不移動其他棋子的情況下，能否完成他的戰略目标。

輸入格式

輸入一共 101010 行，每行一個長度為 999 的字元串。

輸入表示這個棋盤，我們用’.‘表示空位置，用’#'表示該位置有棋子，

用’S’表示初始的馬的位置，用’T’表示馬需要跳到的位置。

輸入保證一定隻存在一個’S’和一個’T’。

輸出格式

如果在不移動其他棋子的情況下，馬能從’S’跳到’T’，樣例輸入 那麼輸出一行"Yes"，否則輸出一行"No"。

樣例輸入

.#....#S#
..#.#.#..
..##.#..#
......##.
...T.....
...#.#...
...#.....
...###...
.........
.##......
           

樣例輸出

Yes

代碼

#include<iostream>
using namespace std;
char maze[15][15];//地圖
int dir[8][2]={{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};//方向
bool vis[15][15];//标記是否走過
bool in(int x,int y){
    return 0<=x&&x<10&&0<=y&&y<9;
}

bool dfs(int x,int y){
    if(maze[x][y]=='T'){
        return true;
    }
    vis[x][y]=true;
    for(int i=0;i<8;i++){
        int tx=x+dir[i][0];
        int ty=y+dir[i][1];
        if(maze[tx][ty]!='#' && in(tx,ty) && !vis[tx][ty]){
            if(dfs(tx,ty)){
                return true;
            }            
        }       
    }
//    vis[x][y]=false;這裡我們如果不取消标記反而可以提高代碼的運作效率。
//因為我們這裡隻需要判斷兩個點是否可達，到達過的狀态就沒有必要再次到達了。
    return false;
}
int main(){
    for(int i=0;i<10;i++){
        cin>>maze[i];
    }
    int x,y;
    for(int i=0;i<10;i++){
        for(int j=0;j<9;j++){
            if(maze[i][j]=='S'){
                x=i;
                y=j;
            }
        }
    }
  //  dfs(x,y)
    if(dfs(x,y)){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    
    return 0;
}
           

2. 踏青

題目描述

樣例輸入

5 6
. # . . . .
. . # . . .
. . # . . #
. . . # # .
. # . . . .
           

樣例輸出

5

代碼