算法题（111）：k与迷宫

审题：
本题需要我们寻找迷宫中的所有出口，若有出口需要输出距离最近的出口的距离，若没有就输出-1

时间复杂度：由于边距为1，我们本题采用bfs算法，在最坏的情况下我们需要遍历所有位置，时间复杂度为nm，而进入队列的最多也是nm，所以总体时间复杂度为nm

思路：

方法一：bfs

首先我们需要分析遍历过程：

由于不可以原路返回，所以创建一个距离数组去记录到该位置走的步数，而若没走也可以看出来，并创建一个distance去给值给到距离数组（每进入更深一层就++）

然后我们还需要记录出口的个数，所以创建一个count负责记录。

解题：

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
typedef pair<int,int> PII;//队列存储的数据类型
int n,m;

由于队列存储的数据是坐标，所以这里需要重命名一个pair<int,int>方便书写

（1）初始化

//录入数据cin >> n >> m;vector<vector<char>> vv(n,vector<char>(m,'.'));//这里其实初始化为什么都可以vector<vector<int>> step(n,vector<int>(m,-1));//记录k到该位置的步数PII start;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){cin >> vv[i][j]; if(vv[i][j] == 'k') start = {i,j};//记录起点坐标}}step[start.first][start.second] = 0;//初始化起点距离值//创建队列queue<PII> q;q.push(start);//建立方向数组vector<vector<int>> d = {{1,0},{-1,0},{0,-1},{0,1}};

step数组主要是用于判断该路是否走过。

（2）入队与搜索

  //bfsint count = 0;//出口数int distance = 1;//距离int mindistance = 1e3;//最短距离while(!q.empty()){int size = q.size();//防止后续进队列的数据影响循环逻辑for(int i = 0; i < size; i++){PII  s = q.front();q.pop();for(auto& e : d){int newx = s.first + e[0];int newy = s.second + e[1];if(newx>=0&&newx<n&&newy>=0&&newy<m&&vv[newx][newy]!='*'&&step[newx][newy]==-1){if(vv[newx][newy] == '.')//没到出口{step[newx][newy] = distance;q.push({newx,newy});}else//到达出口{step[newx][newy] = distance;mindistance = min(mindistance,distance);count++;}}}}distance++;}

当我们遍历到路或者出口，且路径没有被走过，我们就可以走这一步。

若为普通道路：更新距离数组，插入该道路坐标进队列，准备下一轮走

若为出口：更新距离数组，并维护mindistance（因为输出需要距离出口的最短距离），并让出口数++

一层走完表示这一步走完了，让distance++，表示进入下一步

（3）输出结果

    //输出数据if(count != 0) {cout << count << " " << mindistance;}else{cout << -1;}

若有出口（count不为0），输出出口数和最短距离

否则输出-1

kotori和迷宫