题解：P10988 [蓝桥杯 2023 国 Python A] 走方格

· · 题解

题目传送门。

题目涉及算法

BFS广搜（蒟蒻不会用DP）。

大致题意

给你一个整数 N 和一个 N 行 N 列的方格图，每个方格有一个数字。

你有一个小人，它最开始在方格图的 0 行 0 列处，你要让它最快走到 N-1 行 N-1 列处，可以选择的移动规则如下：

  1. 向下走 1 格；
  2. 向右走 1 格；
  3. 向右移动 L 格，格子里的数必须单调递减；
  4. 向左移动 L 格，格子里的数必须单调递减；

注意：不可走出方格图，每走一次耗时 1 秒。

思路解析

很明显，这是一道最短路很水的绿题，这让我们立刻想到了BFS。

BFS模版：

void bfs(void)
{
    q[tt++]={1,1,0};//习惯了从1开始
    vis[1][1]=1;
    while(hh<tt)
    {
        node p=q[hh++];
        if(p.x==n&&p.y==n)
        {
            ans=p.dis;
            return ;
        }
        for(int i=0;i<2;i++)
        {
            int nx=p.x+dx[i];
            int ny=p.y+dy[i];
            if(nx<=n&&ny<=n&&!vis[nx][ny])//没有障碍物特判
            {
                q[tt++]={nx,ny,p.dis+1};
                vis[nx][ny]=1;
            }
        }
    }
}

很明显，普通BFS模板只能解决 1\sim2 两步， 3\sim4 两步则还需要两个for循环：

for(int i=p.y+1;i<=n;i++)//从起始点+1到n
{
  if(a[p.x][i]>=a[p.x][i-1]) break;//不符合立刻退出
  if(!vis[p.x][i])
  {
    q[tt++]={p.x,i,p.dis+1};
    vis[p.x][i]=1;
  }
}
for(int i=p.y-1;i;i--)//从起始点-1到1
{
  if(a[p.x][i]>=a[p.x][i+1]) break;
  if(!vis[p.x][i])
  {
    q[tt++]={p.x,i,p.dis+1};
    vis[p.x][i]=1;
  }
}

有了这些思路，AC代码就出来了：

#include<bits/stdc++.h>
#define N 1010 //养成定义常量的好习惯
using namespace std;
int n,hh,tt,ans;
int a[N][N];
int vis[N][N];
int dx[]={0,1},dy[]={1,0};
struct node{
    int x,y,dis;
}q[N*N];
void bfs(void)
{
    q[tt++]={1,1,0};
    vis[1][1]=1;
    while(hh<tt)
    {
        node p=q[hh++];
        if(p.x==n&&p.y==n)
        {
            ans=p.dis;
            return ;
        }
        for(int i=0;i<2;i++)
        {
            int nx=p.x+dx[i];
            int ny=p.y+dy[i];
            if(nx<=n&&ny<=n&&!vis[nx][ny])
            {
                q[tt++]={nx,ny,p.dis+1};
                vis[nx][ny]=1;
            }
        }
        for(int i=p.y+1;i<=n;i++)
        {
            if(a[p.x][i]>=a[p.x][i-1]) break;
            if(!vis[p.x][i])
            {
                q[tt++]={p.x,i,p.dis+1};
                vis[p.x][i]=1;
            }
        }
        for(int i=p.y-1;i;i--)
        {
            if(a[p.x][i]>=a[p.x][i+1]) break;
            if(!vis[p.x][i])
            {
                q[tt++]={p.x,i,p.dis+1};
                vis[p.x][i]=1;
            }
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++) cin>>a[i][j];
    }
    bfs();
    cout<<ans;
    return 0;
}

谢谢观看，祝你AC！