上海市计算机学会竞赛平台2024年4月月赛丙组数字迷宫

题目描述

给定一个 𝑛×𝑚n×m 的网格数字迷宫，每个网格上有一个数字，第 𝑖i 行、第 𝑗j 列网格上的数字为 𝑎(𝑖,𝑗)a(i,j)​ ，表示走到这个格子后，下一次移动可以往上下左右任一方向走 𝑎(𝑖,𝑗)a(i,j)​ 格。

请问，若从网格左上角 (1,1)(1,1) 位置走到右下角 (𝑛,𝑚)(n,m) 位置，最少需要走多少次？

输入格式

输入第一行，两个正整数分别表示 𝑛,𝑚n,m
接下来的第 22 行至第 𝑛+1n+1 行，每行 𝑚m 个数字，用空格隔开，其中第 𝑖+1i+1 行、第 𝑗j 列的数字表示 𝑎(𝑖,𝑗)a(i,j)​ 。

输出格式

输出一个整数，表示最少步数，若无法达到右下角，则输出 No Solution

数据范围

• 对于 30%30%的数据，1≤𝑛,𝑚≤101≤n,m≤10
• 对于 60%60%的数据，1≤𝑛,𝑚≤1001≤n,m≤100
• 对于 100%100%的数据，1≤𝑛,𝑚≤1031≤n,m≤103，1≤𝑎𝑖≤𝑚𝑎𝑥(𝑛,𝑚)1≤ai​≤max(n,m)

样例数据

输入:

3 4
1 2 3 4
1 1 1 1
2 2 2 2

输出:

3

说明:

(1,1)-->(1,2)-->(3,2)-->(3,4)

详见代码:

#include <bits/stdc++.h>
using namespace std;
struct node 
{
    int x,y,step;
}
queue <node>q;
int n,m;
int a[1005][1005];
bool vis[1005][1005];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void bfs()
{
    vis[1][1]=1;
    node t={1,1,0};
    q.push(t);
    while (!q.empty())
    {
        t=q.front();
        q.pop();
        int x=t.x;
        int y=t.y;
        int step=t.step;
        if (x==n&&y==m)
        {
            cout<<step;
            return;
        }
        for(int i=0;i<4;i++)
        {
            int xx=x+dx[i]*a[x][y];
            int yy=y+dy[i]*a[x][y];
            if (xx>=1&&xx<=n&&yy>=1&&yy<=m&&vis[xx][yy]==0)
            {
                vis[xx][yy]=1;
                q.push({xx,yy,step+1});
            }
        }
    }
    cout<<"No Solution";
    return;
}
int main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }
    bfs();
    return 0;
}