算法(DFS) C++ 代码

//https://www.acwing.com/problem/content/1103/ 
//1是S 0是. 2是# 9是E 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int T,R,C;
bool temp=false;
int maze[200][200],v[200][200];
struct S_and_E{
    int S_a;
    int S_b;
    int count;
    S_and_E(int a,int b,int c): S_a(a),S_b(b),count(c){}
};

queue<S_and_E> x;//队列x

void S(){
    //找白鼠所在位置S 
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            if(maze[i][j]==1){
                v[i][j]=1;
                x.push(S_and_E(i,j,0));
                break;
            }
        }
    }
}
void turn(int a,int b,int c){//移动位置 右上左下 
    int na[4]={0,-1,0,1},nb[4]={1,0,-1,0};
    for(int i=0;i<4;i++){
        int aa = a + na[i];
        int bb = b + nb[i];
        //判断是否越位 或者 位置为# 
        if(v[aa][bb]==1 || maze[aa][bb]==2 || aa<0 || aa>=R || bb<0 || bb>=C) continue;

        v[aa][bb]=1;
        x.push(S_and_E(aa,bb,c+1));//加入队列 次数+1

        if(maze[aa][bb]==9){
            temp=true;
            break;
        }
    }
    x.pop();
}

//BFS
int work(){
    S();
    while(!x.empty()){
        temp=false;
        turn(x.front().S_a,x.front().S_b,x.front().count);
        if(temp==true){
            cout << x.back().count;
            while(!x.empty()) x.pop();//成功吃到奶酪就清空队列
            break;
        }
    }
    if(temp==false){//清空队列
        while(!x.empty()) x.pop();
        cout << "oop!";
    }
}

int main(){
    cin >> T;
    char z;
    while(T--){
        cin >> R >> C;
        for(int i=0;i<R;i++){
            for(int j=0;j<C;j++){
                v[i][j]=0;
                cin >> z;
                if(z=='.') maze[i][j]=0;
                else if(z=='S') maze[i][j]=1;
                else if(z=='#') maze[i][j]=2;
                else if(z=='E') maze[i][j]=9;
            }
        }
        work();
        cout << "\n";
    }

    return 0;
}