迷宫寻路

4 年前

网络安全话题下的优秀答主

题目描述

假设一个探险家被困在了地底的迷宫之中，要从当前位置开始找到一条通往迷宫出口的路径。迷宫可以用一个二维矩阵组成，有的部分是墙，有的部分是路。迷宫之中有的路上还有门，每扇门都在迷宫的某个地方有与之匹配的钥匙，只有先拿到钥匙才能打开门。请设计一个算法，帮助探险家找到脱困的最短路径。如前所述，迷宫是通过一个二维矩阵表示的，每个元素的值的含义如下 0-墙，1-路，2-探险家的起始位置，3-迷宫的出口，大写字母-门，小写字母-对应大写字母所代表的门的钥匙
输入描述:
迷宫的地图，用二维矩阵表示。第一行是表示矩阵的行数和列数M和N 后面的M行是矩阵的数据，每一行对应与矩阵的一行（中间没有空格）。M和N都不超过100, 门不超过10扇。
输出描述:
路径的长度，是一个整数
示例:
输入

输出

问题描述：

矩阵迷宫行数M
矩阵迷宫列数N
0表示墙
1表示路
2表示入口
3表示出口
a-j表示钥匙
A-J表示门

解题思路：

首先找到入口点2，然后dfs广度优先遍历；
入口点入队列，判断队列是否为空，不空，出队列；
拿到队列头节点，头节点坐标为3，找到出口；
否则，遍历头节点上下左右四个方向的下一个节点；
下一个节点坐标超过矩阵范围或者遇到墙了，继续；
如果下一个节点坐标是钥匙，那么捡起钥匙；
如果下一个节点坐标是门，并且没有门的钥匙，继续；
如果下一个节点钥匙状态没有访问过，那么访问这个节点，路径加一，放入队列中。

重复2～8的过程，最终找出走出迷宫的步数。

那么问题来了，为什么bfs（Breadth First Search）算出来的就是迷宫最短路径呢？

#include <iostream>
#include <queue>
#include <stdio.h>
#include <cstring>
using namespace std;
int M,N;
char maze[101][101];
int visited[101][101][1024];
int Next[4][2] = {0,1,0,-1,-1,0,1,0};
struct node{
  int x,y,key,step;
  node(int x,int y,int key,int step):x(x),y(y),key(key),step(step){};  
int bfs(int x,int y)
  queue<node> Q;
  Q.push(node(x,y,0,0));
  while(!Q.empty())
    node head = Q.front();
    Q.pop();
    if(maze[head.x][head.y] == '3')
      return head.step;
    for(int i = 0;i < 4;++i)
      int nx = head.x + Next[i][0];
      int ny = head.y + Next[i][1];
      if(nx >= M || nx < 0 || ny >= N || ny <0 || maze[nx][ny] == '0')
        continue;
      int key = head.key;
      if('a' <= maze[nx][ny] && maze[nx][ny] <= 'z')
        key = key | (1 << (maze[nx][ny] - 'a'));
      if('A' <= maze[nx][ny] && maze[nx][ny] <= 'Z' && (key &( 1 << (maze[nx][ny] - 'A'))) == 0)
        continue;
      if(!visited[nx][ny][key])
        visited[nx][ny][key] = 1;
        Q.push(node(nx,ny,key,head.step+1));
  return 0;    
int main()
  memset(maze,0,sizeof(maze));
  cin >> M >> N;
  for(int i = 0;i < M;++i)
    for(int j =0;j < N;++j)
      cin >> maze[i][j];
  int flag = 0;
  for(int i = 0;i < M;++i)
    if(flag == 1) break;
    for(int j = 0;j < N;++j)
      if(maze[i][j] == '2')
        flag = 1;
        visited[i][j][0] = 1;
        cout << bfs(i,j);
        break;