题目:X星球的一处迷宫游乐场建在某个小山坡上。它是由10x10相互连通的小房间组成的。
房间的地板上写着一个很大的字母。我们假设玩家是面朝上坡的方向站立,则:
L表示走到左边的房间,R表示走到右边的房间,U表示走到上坡方向的房间,D表示走到下坡方向的房间。
X星球的居民有点懒,不愿意费力思考。他们更喜欢玩运气类的游戏。这个游戏也是如此!
开始的时候,直升机把100名玩家放入一个个小房间内。玩家一定要按照地上的字母移动。
迷宫地图如下:
------------
UDDLUULRUL
UURLLLRRRU
RRUURLDLRD
RUDDDDUUUU
URUDLLRRUU
DURLRLDLRL
ULLURLLRDU
RDLULLRDDD
UUDDUDUDLL
ULRDLUURRR
----------------
主要思想:dfs(深度优先搜索) 和递归。
个人思路:
1.先建议一个字符型二维数组place(10*10)来存放方向D,U,L,R;
2.遍历place的每个点,查询该点是否可以走出去。
注意:遍历每个点之前要先初始化FLAG,以防每个点之间的数据相互影响。
3.再建立一个整型二维数组FLAG(12*12),其作用有两个:
一个是为了标记走过的路径,二是为了检查是否走出迷宫。初始化的FLAG如图所示:
1代表已经出迷宫,0代表还在迷宫内 ,当走过一个点时,将0修改为INF。INF的意思已经走过的点。
4.如果已经走出迷宫直接返回1,如果已经进入循环则返回0,其他情况则根据当前迷宫格的情况继续行走。如果继续走的情况则先将该点的标志数组的值变为INF,然后递归DFS函数。
代码如下:
#include<iostream>
using namespace std;
char place[12][12];
int FLAG[12][12];
const int INF = 2;
int peoplenum = 0;
bool dfs(int x, int y, char M) {
//如果进入已经经过的点,就返回0
if (FLAG[x][y] == INF) return 0;
//如果已经出迷宫就返回1
else if (FLAG[x][y] == 1) return 1;
//可以继续走的情况
//nx,ny分别表示下一个点的行和列
if (FLAG[x][y] == 0) {
//U为向上走,y不变,x减少1
if (M == 'U') {
//将该点在标志数组中所对应的位置的值变为INF
FLAG[x][y] = INF;
int nx = x - 1;
int ny = y;
return dfs(nx, ny, place[nx][ny]);
}
//D为向下走,y不变,x加上1
if (M == 'D') {
FLAG[x][y] = INF;
int nx = x + 1;
int ny = y;
return dfs(nx, ny, place[nx][ny]);
}
//R为向右走,x不变,y加1
if (M == 'R') {
FLAG[x][y] = INF;
int nx = x;
int ny = y + 1;
return dfs(nx, ny, place[nx][ny]);
}
if (M == 'L')
//L为向左走,x不变,y-1
{
FLAG[x][y] = INF;
int nx = x;
int ny = y - 1;
return dfs(nx, ny, place[nx][ny]);
}
}
return 0;
}
void chongzhi() {
//标志数组先全定位0
for (int i = 0; i <= 11; i++) {
for (int j = 0; j <= 11; j++) {
FLAG[i][j] = 0;
}
}
//对第0和11列特殊赋值为1
for (int i = 0; i <= 11; i++) {
FLAG[i][0] = 1;
FLAG[i][11] = 1;
}
//对第0行和11特殊赋值为1
for (int i = 0; i <= 11; i++) {
FLAG[0][i] = 1;
FLAG[11][i] = 1;
}
}
void solve() {
for (int h = 1; h <= 10; h++)
for (int l = 1; l <= 10; l++) {
//查询新的迷宫格,重置标志数组
chongzhi();
//调用dfs函数,如果返回1则说明该迷宫格可以走出去,那么走出去的人数则加上1
if (dfs(h, l, place[h][l])) peoplenum++;
}
cout << peoplenum;
}
int main() {
//输入迷宫的情况
for (int i = 1; i <= 10; i++)
for (int j = 1; j <= 10; j++) {
cin >> place[i][j];
}
solve();
return 0;
}
个人心得:
1.一开始犯错的点在U向上的写成-1,D向下写成+1。导致答案错误。
2.开一个标志数组个人认为比较方便一些,因为要检查是否已经经过的该迷宫点和迷宫边界比较难处理。文章来源:https://www.toymoban.com/news/detail-414264.html
留言:还有一些不足和可以优化的地方,有建议可指教一下~文章来源地址https://www.toymoban.com/news/detail-414264.html
到了这里,关于蓝桥杯(迷宫问题)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!