专栏文章

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

LLuojt95
P10988题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipxryqf
此快照首次捕获于
2025/12/03 19:41
3 个月前
此快照最后确认于
2025/12/03 19:41
3 个月前
查看原文
题目传送门。

题目涉及算法

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

大致题意

给你一个整数 NN 和一个 NN 行 NN 列的方格图，每个方格有一个数字。
你有一个小人，它最开始在方格图的 00 行 00 列处，你要让它最快走到 N−1N-1 行 N−1N-1 列处，可以选择的移动规则如下：
  1. 向下走 11 格；
  2. 向右走 11 格；
  3. 向右移动 LL 格，格子里的数必须单调递减；
  4. 向左移动 LL 格，格子里的数必须单调递减；
注意：不可走出方格图，每走一次耗时 11 秒。

思路解析

很明显，这是一道最短路很水的绿题，这让我们立刻想到了BFS。
BFS模版：
CPP
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∼21\sim2 两步， 3∼43\sim4 两步则还需要两个for循环：
CPP
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代码就出来了：
CPP
#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！

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...