题解 | #棋盘游戏#

#include <bits/stdc++.h>
#define MAX 10
#define INF 0x3f3f3f3f
using namespace std;

int matrix[6][6];
int a[] = {1, -1, 0, 0}; //向上向下
int b[] = {0, 0, -1, 1}; //向左向右
int ans = INF, tmp;     //tmp是记录总代价的临时变量
int visited[6][6];

void dfs(int x, int y, int x2, int y2, int status, int tmp) {
    if (x == x2 && y == y2)
        ans = min(ans, tmp);
    else {
        visited[x][y] = 1;  //标记已访问
        for (int i = 0; i < 4; i++) {
            int newx = x + a[i];    //新坐标
            int newy = y + b[i];    //新坐标
            if (newx > 5 || newx < 0 || newy > 5 || newy < 0 || visited[newx][newy]) //新坐标超出棋盘
                continue;
            int cost = matrix[newx][newy] * status; //此步代价
//          tmp += cost;
            int newstatus = (cost % 4) + 1;
            dfs(newx, newy, x2, y2, newstatus, tmp + cost);
        }
    }
    visited[x][y] = 0;  //重置环境
}

int main() {

    int x, y, x2, y2, i, j, status = 1;
    for (i = 0; i < 6; i++)
        for (j = 0; j < 6; j++)
            cin >> matrix[i][j];
    cin >> x >> y >> x2 >> y2;
    memset(visited, 0, sizeof(visited));
    dfs(x, y, x2, y2, status, 0);
    cout << ans;
}