题解 | #棋盘游戏#

#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int x2, y2;//终点
int chess[6][6];
bool visited[6][6];
int min_cost =INT16_MAX;
void dfs(int x,int y,int cost,int cur_state)
{
    //收集结果
    if (x == x2 && y == y2)
    {
        min_cost = min(min_cost,cost);
        return;
    }
    //剪枝
    if (cost > min_cost)
    {
        return;
    }
    //向下 cur_state * chess[x+1][y]是当前步的花销
    if (x < 5&& visited[x + 1][y] == 0)
    {
            visited[x+1][y] = 1;
            dfs(x+1,y, cost + cur_state * chess[x+1][y], (cur_state * chess[x+1][y]) % 4 + 1);
            visited[x+1][y] = 0;
    }
    //向右
    if (y < 5&& visited[x][y+1] == 0)
    {
            visited[x][y+1] = 1;
            dfs(x,y+1, cost + cur_state * chess[x][y + 1], ( cur_state * chess[x][y + 1]) % 4 + 1);
            visited[x][y + 1] = 0;
    }
    //向左
    if (y > 0&& visited[x][y - 1] == 0)
    {

            visited[x][y - 1] = 1;
            dfs(x,y-1, cost + cur_state * chess[x][y - 1], ( cur_state * chess[x][y - 1]) % 4 + 1);
            visited[x][y - 1] = 0;
    }
    //向上
    if (x > 0&& visited[x - 1][y] == 0)
    {
            visited[x-1][y] = 1;
            dfs(x-1,y, cost + cur_state * chess[x - 1][y], ( cur_state * chess[x - 1][y]) % 4 + 1);
            visited[x - 1][y] = 0;
    }
}

int main() {
    for (int i = 0; i < 6; i++)
    {
        for (int j = 0; j < 6; j++)
        {
            cin >> chess[i][j];
        }
    }
    for (int i = 0; i < 6; i++)
    {
        for (int j = 0; j < 6; j++)
        {
            visited[i][j] = 0;
        }
    }
    int x1, y1;//起点
    cin >> x1 >> y1 >> x2 >> y2;
    visited[x1][y1] = 1;
    dfs(x1,y1,0,1);
    cout << min_cost << endl;
}
// 64 位输出请用 printf("%lld")