指针原来是套娃的


私信TA

用户名:uq_92467646842

访问量:9779

签 名:

数学改变科学,科学改变世界

等  级
排  名 19
经  验 14516
参赛次数 40
文章发表 96
年  龄 0
在职情况 学生
学  校
专  业 物联网工程

  自我简介:

QQ:2830671713

解题思路:
因为不知道怎么打印路径所以不会做这道题,看了一些题解才明白,当前位置储存上一个位置,记录是从哪里走来的,然后再倒序寻找前面的坐标。

不过这个倒序寻找太麻烦了,这是我按照题解写的倒序寻找

image.png

逻辑还算清楚,但是写起来实在麻烦。

直到我做了这道题1923: 蓝桥杯算法提高VIP-学霸的迷宫,是用的在结构体里放置一个存储数组,数组记录从开始到现在的位置,打印的时候直接遍历输出就可以了。

感觉这道题可以这么做,所以在结构体里放置了一个string(因为string打印方便,存放的时候不需要像数组一样获取长度存储),然后用string记录从0,0到4,4的每一步,然后直接输出。

因为不是简单的bfs找长度,所以我就不解释bfs模板了,详见代码注释。
参考代码:

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

const int S=5;

struct node{
	int x,y;
	string s; //存放位置
};

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

bool vis[S][S];
int p[S][S];
queue<node>q;

void bfs(int n,int m){
	q.push(node{0,0}); //开始在0,0处
	
	while(!q.empty()){
		
		node now=q.front();//获取队首位置
		vis[now.x][now.y]=1;
		q.pop();
		
		if(now.x==n-1&&now.y==m-1){
			for(int i=0;i<now.s.size();i+=2){//打印
				cout<<"("<<now.s[i]<<", "<<now.s[i+1]<<")"<<endl;
			}
			cout<<"(4, 4)";//因为不存放自身的位置,所以需要单独打印
			break;
		}
		for(int i=0;i<4;i++){
			int x=now.x+dx[i];
			int y=now.y+dy[i];
			if(x>=0&&y>=0&&x<n&&y<m){//不超过数组大小
				if(p[x][y]==0&&vis[x][y]==0){//可以走且没有走过
					vis[x][y]=1;
					node nom=now;//现在num.s已经存放了now.s记录的位置(核心代码)
					nom.x=x;
					nom.y=y;
					nom.s+=now.x+'0';//将上一步的位置坐标新增到s里面(核心代码)
					nom.s+=now.y+'0';
					q.push(nom);
				}
			}	
		}
	}
}

int main()
{
	int n=5,m=5;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++)cin>>p[i][j];
	}

	bfs(n,m);
 	return 0;
}

这道题打印的时候需要注意,是英文符号,而且,后面有个空格。

以上。

 

0.0分

5 人评分

  评论区