迷宫寻路

119 阅读 0 评论 79 点赞

我是靠谱客的博主忧心草莓，最近开发中收集的这篇文章主要介绍迷宫寻路，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述

假设一个探险家被困在了地底的迷宫之中，要从当前位置开始找到一条通往迷宫出口的路径。迷宫可以用一个二维矩阵组成，有的部分是墙，有的部分是路。迷宫之中有的路上还有门，每扇门都在迷宫的某个地方有与之匹配的钥匙，只有先拿到钥匙才能打开门。请设计一个算法，帮助探险家找到脱困的最短路径。如前所述，迷宫是通过一个二维矩阵表示的，每个元素的值的含义如下 0-墙，1-路，2-探险家的起始位置，3-迷宫的出口，大写字母-门，小写字母-对应大写字母所代表的门的钥匙

输入描述:

迷宫的地图，用二维矩阵表示。第一行是表示矩阵的行数和列数M和N
后面的M行是矩阵的数据，每一行对应与矩阵的一行（中间没有空格）。M和N都不超过100, 门不超过10扇。

输出描述:

路径的长度，是一个整数

示例1

输入

复制

输出

复制

7



因为会出现需要为了捡钥匙对某个点重复踩多次的情况，所以vis[i][j]无法确认该点是否下次还需要访问，故需要扩充vis状态数组。
用二进制的形式，0101000000，表示已经拥有第二把和第四把钥匙，最多十把钥匙，最多有1024种状态，故vis[i][j][1024]可以确认一个点的访问状态。

相当于每次捡到一把钥匙后，都重置一次vis[i][j]数组，同时不影响其他钥匙状态的vis[i][j]数组



超时:忘记在搜到出口后 立刻结束bfs

#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
using namespace std;
char mp[105][105];
//扩充了vis的状态，解决了需要回头捡钥匙，又要避免bfs重复加入队列的情况
//赋予每个点(i,j)不同的意义，不再是单纯的是否访问过 ，bfs的核心之一
bool vis[105][105][1024];
//vis[i][j][key]
key是二进制，表示有无见到某种钥匙，0000100001(33)，表示拥有第1把和第6把钥匙
int toInt(string s)
//二进制转为十进制 
{
int t = 0,ans = 0;
for(int i=s.length()-1;i>=0;i--){
ans += (s[i]-'0')*pow(2,t);
t++;
}
return ans;
}
struct F
{
int x,y;
}f[4];
struct Node
{
int posi,posj;
//该点坐标
int step;
//行至该点花费的步数

string key;
//该点目前携带的钥匙状态的二进制

}temp;
int m,n,minn=100000000;
int bgposi,bgposj;
//开始点 
queue<Node> q;
void bfs()
{
vis[bgposi][bgposj][0] = true;
temp.posi = bgposi;
temp.posj = bgposj;
temp.step = 0;
temp.key = "0000000000";
q.push(temp);
while(!q.empty())
{
temp = q.front();
q.pop();
int i = temp.posi;
int j = temp.posj;
int step = temp.step;
if(mp[i][j] == '3')
{
if(step < minn)
minn = step;
continue;
}
string key = temp.key;
int state = toInt(key);
cout<<i<<" "<<j<<" "<<state<<endl;
for(int p=0;p<4;p++)
{
int tempi = i+f[p].x;
int tempj = j+f[p].y;
if(tempi>=0 && tempi<m && tempj>=0 && tempj<n && vis[tempi][tempj][state]==false && mp[tempi][tempj]!='0')
{
vis[tempi][tempj][state] = true;
if(mp[tempi][tempj]>='A' && mp[tempi][tempj]<='Z' && key[mp[tempi][tempj]-'A'] == '1')
{
temp.posi = tempi;
temp.posj = tempj;
temp.step = step+1;
q.push(temp);
}
else if(mp[tempi][tempj]>='a' && mp[tempi][tempj]<='z')
{
temp.posi = tempi;
temp.posj = tempj;
temp.step = step+1;
temp.key[mp[tempi][tempj]-'a'] = '1';
q.push(temp);
}
else if(mp[tempi][tempj] == '1' || mp[tempi][tempj] == '2' || mp[tempi][tempj] == '3')
{
temp.posi = tempi;
temp.posj = tempj;
temp.step = step+1;
q.push(temp);
}
}
}
}
}
int main()
{
cin>>m>>n;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
{
cin>>mp[i][j];
if(mp[i][j] == '2')
{
bgposi = i;
bgposj = j;
}
}
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
for(int k=0;k<1024;k++)
vis[i][j][k] = false;
f[0].x = -1;f[0].y = 0;
f[1].x = 1;f[1].y = 0;
f[2].x = 0;f[2].y = -1;
f[3].x = 0;f[3].y = 1;
bfs();
cout<<minn<<endl;
return 0;
}

#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
using namespace std;
char mp[105][105];
//扩充了vis的状态，解决了需要回头捡钥匙，又要避免bfs重复加入队列的情况
//赋予每个点(i,j)不同的意义，不再是单纯的是否访问过 ，bfs的核心之一
bool vis[105][105][1024];
//vis[i][j][key]
key是二进制，表示有无见到某种钥匙，0000100001(33)，表示拥有第1把和第6把钥匙
int toInt(string s)
//二进制转为十进制 
{
int t = 0,ans = 0;
for(int i=s.length()-1;i>=0;i--){
ans += (s[i]-'0')*pow(2,t);
t++;
}
return ans;
}
struct F
{
int x,y;
}f[4];
struct Node
{
int posi,posj;
//该点坐标
int step;
//行至该点花费的步数

string key;
//该点目前携带的钥匙状态的二进制

}temp;
int m,n;
int bgposi,bgposj;
//开始点 
queue<Node> q;
void bfs()
{
vis[bgposi][bgposj][0] = true;
temp.posi = bgposi;
temp.posj = bgposj;
temp.step = 0;
temp.key = "0000000000";
q.push(temp);
while(!q.empty())
{
temp = q.front();
q.pop();
int i = temp.posi;
int j = temp.posj;
int step = temp.step;
/*
错误：在保证是一步步搜索的情况下 ，bfs保证步数最少，直接退出
if(mp[i][j] == '3')
{
if(step < minn)
minn = step;
continue;
}*/
if(mp[i][j] == '3'){
cout<<step;
return;
}
string key = temp.key;
int state = toInt(key);
//cout<<i<<" "<<j<<" "<<state<<endl;
for(int p=0;p<4;p++)
{
int tempi = i+f[p].x;
int tempj = j+f[p].y;
if(tempi>=0 && tempi<m && tempj>=0 && tempj<n && vis[tempi][tempj][state]==false && mp[tempi][tempj]!='0')
{
vis[tempi][tempj][state] = true;
if(mp[tempi][tempj]>='A' && mp[tempi][tempj]<='Z' && key[mp[tempi][tempj]-'A'] == '1')
{
temp.posi = tempi;
temp.posj = tempj;
temp.step = step+1;
q.push(temp);
}
else if(mp[tempi][tempj]>='a' && mp[tempi][tempj]<='z')
{
temp.posi = tempi;
temp.posj = tempj;
temp.step = step+1;
temp.key[mp[tempi][tempj]-'a'] = '1';
q.push(temp);
}
else if(mp[tempi][tempj] == '1' || mp[tempi][tempj] == '2' || mp[tempi][tempj] == '3')
{
temp.posi = tempi;
temp.posj = tempj;
temp.step = step+1;
q.push(temp);
}
}
}
}
}
int main()
{
cin>>m>>n;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
{
cin>>mp[i][j];
if(mp[i][j] == '2')
{
bgposi = i;
bgposj = j;
}
}
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
for(int k=0;k<1024;k++)
vis[i][j][k] = false;
f[0].x = -1;f[0].y = 0;
f[1].x = 1;f[1].y = 0;
f[2].x = 0;f[2].y = -1;
f[3].x = 0;f[3].y = 1;
bfs();
return 0;
}