摘要
Title: 3480. 棋盘游戏
Tag: BFS, DFS
Memory Limit: 64 MB
Time Limit: 1000 ms

3480. 棋盘游戏

题意

有一个 6×6的棋盘，棋盘的每个位置上都有一个数值，现在有一个起始位置和终止位置，请找出一个从起始位置到终止位置代价最小的路径：
只能沿上下左右四个方向移动。
总代价是每走一步的代价之和。
每步（从 (a,b)到 (c,d)）的代价是 (c,d)上的数值与其在 (a,b)上的状态的乘积。
初始状态为 1，每走一步，状态按如下公式变化：(走这步的代价mod4)+1
思路

数据不是很大
直接暴力BFS或DFS，这里采用BFS
- 由于可以走回来，所以不能开vis数组
- 优化：当前状态的代价已经比答案大了，就直接pop出去

代码

/*
* @Author: NEFU AB-IN
* @Date: 2023-05-02 16:39:28
* @FilePath: \Acwing\3480\3480.cpp
* @LastEditTime: 2023-05-02 16:58:31
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 10, INF = 0x3f3f3f3f;

int g[N][N];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};

struct sa
{
    int x, y, c, w;
};

signed main()
{
    IOS;
    for (int i = 0; i < 6; ++i)
    {
        for (int j = 0; j < 6; ++j)
        {
            cin >> g[i][j];
        }
    }

    int sx, sy, ex, ey;
    cin >> sx >> sy >> ex >> ey;
    int ans = INF;
    queue<sa> q;
    q.push({sx, sy, 0, 1});

    while (SZ(q))
    {
        auto t = q.front();
        q.pop();

        int x = t.x, y = t.y, c = t.c, w = t.w;
        if (x == ex && y == ey)
        {
            ans = min(ans, c);
            continue;
        }
        if (c > ans)
            continue;

        for (int i = 0; i < 4; ++i)
        {
            int a = x + dx[i];
            int b = y + dy[i];

            if (a < 0 || a > 5 || b < 0 || b > 5)
                continue;

            int cn = c + w * g[a][b];
            int wn = (w * g[a][b] % 4) + 1;
            q.push({a, b, cn, wn});
        }
    }

    cout << ans;

    return 0;
}

3480. 棋盘游戏

题意

思路

代码