题解 | #棋盘游戏#

#include<iostream>
#include<cstring>
using namespace std;
int g[6][6];
bool st[6][6];
int c=0;
int res = 1e8;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int sx,sy,ex,ey; //起点坐标和终点坐标

void dfs(int x,int y,int state,int cost){
    if(x==ex&&y==ey){ //到达终点，更新cost
        if(cost<res) res = cost;
        return;
    }
    if(cost>res) return; //枝剪
    st[x][y] = true;
    for(int i=0;i<4;i++){
        int nx=x+dx[i],ny=y+dy[i];
        if(nx<0||nx>5||ny<0||ny>5||st[nx][ny]) continue;
        c=g[nx][ny]*state;
        dfs(nx,ny,(c%4)+1,cost+c);
        st[nx][ny] = false;
    }
    
}
int main(){
    for(int i=0;i<6;i++)
        for(int j=0;j<6;j++) cin>>g[i][j];
    cin>>sx>>sy>>ex>>ey;
    memset(st,false,sizeof st);
    dfs(sx,sy,1,0);
    cout<<res<<endl;
    return 0;
}