迷宫寻宝路线-Toy模板网

这篇具有很好参考价值的文章主要介绍了迷宫寻宝路线。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述

小码君是一名游戏开发者，他正在开发一个基于二维 n×n 的迷宫游戏。

他需要编写一个算法：从游戏地图的左上角开始进行搜索，并按搜索上下左右的顺序输出所有经过的格子上的数字，以确保所有格子都被搜索到。

这些数字代表了游戏中的关键信息，例如宝藏位置、怪物位置、陷阱位置等。通过这个算法，可以帮助玩家找到所有的宝藏并击败所有的怪物，顺利通过迷宫。

输入格式

输入一个整数 n 表示数字迷宫阵列为n∗n

下一行开始，共 n 行，每行 n 个数字

输出格式

共 n∗n 个整数，每两个整数之间用一个空格隔开，顺序是搜索的顺序

样例输入

样例输出

1 5 2 9 6 3 3 0 7 4 4 1 8 5 2 6

样例输入

样例输出

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

说明提示

n 不超过 100文章来源地址https://www.toymoban.com/news/detail-622294.html

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N = 105;
struct node{
	int x, y, step;
};
queue<node> q;
int dir[4][2] = {1, 0, 0, 1, 0, -1, -1, 0};
int n, maps[N][N];
bool vis[N][N]; // 标记数组 
void bfs(){
	//1 起点入队列 
	q.push({1, 1, 0});
	vis[1][1] = true;
	//2 取出队头，出队
	while(q.size()){
		node nd = q.front();
		q.pop();
		int x = nd.x;
		int y = nd.y;
		cout << maps[x][y] << " ";
		for(int i=0; i<4; i++){
			int nx = x + dir[i][0];
			int ny = y + dir[i][1];
			if(maps[nx][ny] == -1 || vis[nx][ny]) continue;
			q.push({nx, ny, nd.step+1});
			vis[nx][ny] = true;
		}
	} 
	//3 终点 / 无解 
}
int main(){
	cin>>n;
	memset(maps, -1, sizeof maps); // -1表示墙 
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			cin>>maps[i][j];
		}
	}
	bfs();

	return 0;
}

到了这里，关于迷宫寻宝路线的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！