上海计算机学会 2024年4月月赛 丙组T5 数字迷宫

第五题：T5数字迷宫

标签：$bfs$
题意：给定一个$n$ x $m$的数字迷宫，每个位置有一个数字$a[i][j]$，表示走到该格子之后，可以往上下左右任意方向移动$a[i][j]$的距离。求从$(1,1)$移动到$(n,m)$位置，最少需要走多少次。
题解：裸的$bfs$，在基础模板上改下变化的新移动位置即可。
代码：

#include <bits/stdc++.h>
using namespace std;

int n, m, a[1005][1005];
int vis[1005][1005];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

struct node {
    int x, y, step;
};

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
    cin >> a[i][j];

    queue<node> q;
    q.push({1, 1, 0});
    vis[1][1] = 1;

    while (!q.empty()) {
        node cur = q.front();
        if (cur.x == n && cur.y == m) {
            cout << cur.step << endl;
            return 0;
        }
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = cur.x + a[cur.x][cur.y] * dx[i];
            int ny = cur.y + a[cur.x][cur.y] * dy[i];
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
            if (vis[nx][ny]) continue;
            vis[nx][ny] = 1;
            q.push({nx, ny, cur.step + 1});
        }
    }

    cout << "No Solution" << endl;
    return 0;
}