C++ APCS實作題 2019/06/15 2 : 機器人走迷宮

有意點點類似 BFS ，不過一次只會有一個分支，以下是程式碼

#include<iostream>
#include<deque>

#define MAX 1000000
using namespace std;

struct step{
    long long x,y;
};

int main(){
    int n,m,min=MAX+1;
    cin>>n>>m;
    long long sum=0;
    step best;
    int mp[110][110]={MAX};

    for(int i=0;i<110;i++){
        for(int j=0;j<110;j++){
            mp[i][j]=MAX;
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>mp[i][j];
            if(min>mp[i][j]){
                min=mp[i][j];
                best.x=j;best.y=i;sum=min;
            } 
        }
    }

    deque<step> st;
    st.push_front(best);
    const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

    while(!st.empty()){
        step now=st.back();
        st.pop_back();

        min=MAX;

        mp[now.y][now.x]=MAX;
        for(int i=0;i<4;i++){
            step next;
            next.x=now.x+dx[i];
            next.y=now.y+dy[i];
            if(mp[next.y][next.x]<min){
                min=mp[next.y][next.x];
                best.x=next.x;best.y=next.y;
            } 
        }
        if(min==MAX){
            continue;
        }else{
            sum+=mp[best.y][best.x];
            st.push_front(best);
        }

    }
    cout<<sum;
    return 0;
}