拼多多 迷宫寻路 dfs
题目描述
假设一个探险家被困在了地底的迷宫之中，要从当前位置开始找到一条通往迷宫出口的路径。迷宫可以用一个二维矩阵组成，有的部分是墙，有的部分是路。迷宫之中有的路上还有门，每扇门都在迷宫的某个地方有与之匹配的钥匙，只有先拿到钥匙才能打开门。请设计一个算法，帮助探险家找到脱困的最短路径。如前所述，迷宫是通过一个二维矩阵表示的，每个元素的值的含义如下 0-墙，1-路，2-探险家的起始位置，3-迷宫的出口，大写字母-门，小写字母-对应大写字母所代表的门的钥匙
输入描述:
迷宫的地图，用二维矩阵表示。第一行是表示矩阵的行数和列数M和N
后面的M行是矩阵的数据，每一行对应与矩阵的一行（中间没有空格）。M和N都不超过100, 门不超过10扇。输出描述:
路径的长度，是一个整数示例1
输入
5 5
02111
01a0A
01003
01001
01111输出
7#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 105;
char map[maxn][maxn];
bool vis[maxn][maxn][1024];
int m,n;
void bfs(int a,int b);
bool judge(int b,int a) //判断坐标是否越界
{
if(a<0 || a>=n || b<0 || b>=m)
{
return false;
}else
{
return true;
}
}
struct node
{
int x,y; //坐标
int ans; //当前的步数
int key;
};
int main()
{
while(cin>>m>>n)
{
memset(vis,0,sizeof(vis));
for(int i=0;i<m;++i)
{
scanf("%s",map[i]);
}
int a,b;
for(int i=0;i<m;++i)
{
for(int j=0;j<n;++j)
{
if(map[i][j]=='2')
{
a=i,b=j;
}
}
}
vis[a][b][0]=1;
bfs(a,b);
}
return 0;
}
void bfs(int a,int b)
{
node st;
st.x=a,st.y=b,st.ans=0;
queue<node> q;
q.push(st);
while(!q.empty())
{
st=q.front();
q.pop();
int pa,pb;
pa=st.x; //Pa和pb为当前坐标
pb=st.y;
//cout<<pa<<" "<<pb<<" "<<st.key<<" "<<st.ans<<endl;
if(map[pa][pb]=='3') //
{
cout<<st.ans<<endl;
break;
}
node temp;
temp.ans=st.ans+1;
int k;
// pa+1 pb
k=st.key;
temp.x=pa+1;
temp.y=pb;
temp.key=k;
if(judge(pa+1,pb)) //如果没越界的话
{
if(map[pa+1][pb]=='3')
{
q.push(temp);
}
else
{
if(map[pa+1][pb]<='z' && map[pa+1][pb]>='a') //如果是钥匙的话
{
k=k|(1<<(map[pa+1][pb]-'a')); //更新这个钥匙状态
temp.key=k;
if(!vis[pa+1][pb][k]) //如果这个状态不存在的话
{
vis[pa+1][pb][k]=1;
q.push(temp);
}
}
else if(map[pa+1][pb]<='Z' && map[pa+1][pb]>='A') //如果是门的话
{
if(k & (1<<(map[pa+1][pb]-'A'))) //并且有钥匙的话
{
if(!vis[pa+1][pb][k]) //如果这个状态不存在的话
{
vis[pa+1][pb][k]=1;
q.push(temp);
}
}
}else if(map[pa+1][pb]=='1')
{
if(!vis[pa+1][pb][k]) //如果这个状态不存在的话
{
vis[pa+1][pb][k]=1;
q.push(temp);
}
}else if(map[pa+1][pb]=='2')
{
if(!vis[pa+1][pb][k]) //如果这个状态不存在的话
{
vis[pa+1][pb][k]=1;
q.push(temp);
}
}
}
}
//pa-1 pb
k=st.key;
temp.x=pa-1;
temp.y=pb;
temp.key=k;
if(judge(pa-1,pb)) //如果没越界的话
{
if(map[pa-1][pb]=='3')
{
q.push(temp);
}
else
{
if(map[pa-1][pb]<='z' && map[pa-1][pb]>='a') //如果是钥匙的话
{
k=k|(1<<(map[pa-1][pb]-'a')); //更新这个钥匙状态
temp.key=k;
if(!vis[pa-1][pb][k]) //如果这个状态不存在的话
{
vis[pa-1][pb][k]=1;
q.push(temp);
}
}
else if(map[pa-1][pb]<='Z' && map[pa-1][pb]>='A') //如果是门的话
{
if(k & (1<<(map[pa-1][pb]-'A'))) //并且有钥匙的话
{
if(!vis[pa-1][pb][k]) //如果这个状态不存在的话
{
vis[pa-1][pb][k]=1;
q.push(temp);
}
}
}else if(map[pa-1][pb]=='1')
{
if(!vis[pa-1][pb][k]) //如果这个状态不存在的话
{
vis[pa-1][pb][k]=1;
q.push(temp);
}
}else if(map[pa-1][pb]=='2')
{
if(!vis[pa-1][pb][k]) //如果这个状态不存在的话
{
vis[pa-1][pb][k]=1;
q.push(temp);
}
}
}
}
//pa pb+1
k=st.key;
temp.x=pa;
temp.y=pb+1;
temp.key=k;
if(judge(pa,pb+1)) //如果没越界的话
{
if(map[pa][pb+1]=='3')
{
q.push(temp);
}
else
{
if(map[pa][pb+1]<='z' && map[pa][pb+1]>='a') //如果是钥匙的话
{
k=k|(1<<(map[pa][pb+1]-'a')); //更新这个钥匙状态
temp.key=k;
if(!vis[pa][pb+1][k]) //如果这个状态不存在的话
{
vis[pa][pb+1][k]=1;
q.push(temp);
}
}
else if(map[pa][pb+1]<='Z' && map[pa][pb+1]>='A') //如果是门的话
{
if(k & (1<<(map[pa][pb+1]-'A'))) //并且有钥匙的话
{
if(!vis[pa][pb+1][k]) //如果这个状态不存在的话
{
vis[pa][pb+1][k]=1;
q.push(temp);
}
}
}else if(map[pa][pb+1]=='1')
{
if(!vis[pa][pb+1][k]) //如果这个状态不存在的话
{
vis[pa][pb+1][k]=1;
q.push(temp);
}
}
else if(map[pa][pb+1]=='2')
{
if(!vis[pa][pb+1][k]) //如果这个状态不存在的话
{
vis[pa][pb+1][k]=1;
q.push(temp);
}
}
}
}
//pa pb-1
k=st.key;
temp.x=pa;
temp.y=pb-1;
temp.key=k;
if(judge(pa,pb-1)) //如果没越界的话
{
if(map[pa][pb-1]=='3')
{
q.push(temp);
}
else
{
if(map[pa][pb-1]<='z' && map[pa][pb-1]>='a') //如果是钥匙的话
{
k=k|(1<<(map[pa][pb-1]-'a')); //更新这个钥匙状态
temp.key=k;
if(!vis[pa][pb-1][k]) //如果这个状态不存在的话
{
vis[pa][pb-1][k]=1;
q.push(temp);
}
}
else if(map[pa][pb-1]<='Z' && map[pa][pb-1]>='A') //如果是门的话
{
if(k & (1<<(map[pa][pb-1]-'A'))) //并且有钥匙的话
{
if(!vis[pa][pb-1][k]) //如果这个状态不存在的话
{
vis[pa][pb-1][k]=1;
q.push(temp);
}
}
}else if(map[pa][pb-1]=='1')
{
if(!vis[pa][pb-1][k]) //如果这个状态不存在的话
{
vis[pa][pb-1][k]=1;
q.push(temp);
}
}
else if(map[pa][pb-1]=='2')
{
if(!vis[pa][pb-1][k]) //如果这个状态不存在的话
{
vis[pa][pb-1][k]=1;
q.push(temp);
}
}
}
}
}
return ;
}
/*
6 10
a110000011
0021111110
11101000A0
1001100111
100B000101
11030001b1
*/