题解 | 棋盘游戏

#include <iostream>
#define ARC 6
#define INT_MAX 400
using namespace std;
const int dx[4]={-1,0,0,1};
const int dy[4]={0,-1,1,0};
int a,b,c,d;
int mapchess[ARC][ARC];
void dfs(int &curMin,int sum,int state,int curX,int curY){
    if(sum>=curMin){
        return;
    }
    if(curX==c&&curY==d){
        if(sum<curMin){
            curMin=sum;
        }
        return;
    }
    for(int i=0;i<4;i++){
        int nextX=curX+dx[i];
        int nextY=curY+dy[i];
        if(nextX>=0&&nextX<ARC&&nextY>=0&&nextY<ARC){
            if(sum+state*mapchess[nextX][nextY]<curMin){
                dfs(curMin,sum+state*mapchess[nextX][nextY],state*mapchess[nextX][nextY]%4+1,nextX,nextY);
            }
        }
    }
}
int main(){
        for(int i=0;i<ARC;i++){
            for(int j=0;j<ARC;j++){
                cin>>mapchess[i][j];
            }
        }
        cin>>a>>b>>c>>d;
        int curMin=INT_MAX;
        dfs(curMin,0,1,a,b);
        cout<<curMin<<endl;
}