BFS专题7 多终点迷宫问题

题目：

样例：

输入

3 3 0 0 0 1 0 0 0 1 0

输出

0 1 2 -1 2 3 -1 -1 4

思路：

        单纯的 BFS 迷宫问题，只是标记一下每个点的 step，注意初始化答案数组都为 -1.

代码详解如下：

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_map>
#define endl '\n'
#define x first
#define y second
#define mk make_pair
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;// 坐标
using PII = pair<int,int>;const int N = 500;// 地图
int n,m;
int g[N][N];// 答案步数数组
int ans[N][N];// 标记走动的坐标
bool st[N][N];// 控制方向坐标
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};// 坐标走动条件
inline bool isRun(int &x,int &y)
{return (~x && ~y && x < n && y < m && !g[x][y] && !st[x][y]);
}inline void BFS()
{int step = 0;queue<PII>q;// 存储起点q.push(mk(0,0));// 开始BFSwhile(q.size()){int sz = q.size();while(sz--){auto now = q.front();q.pop();// 标记答案步数数组ans[now.x][now.y] = step;// 标记当前走动的坐标st[now.x][now.y] = true;// 开始寻找走动方向的坐标for(int i = 0;i < 4;++i){int bx = now.x + dx[i];int by = now.y + dy[i];// 如果可以走动该方向if(isRun(bx,by)){// 标记并存储st[bx][by] = true;q.push(mk(bx,by));}}}++step;}
}// 输出答案步数数组
inline void PrintAns()
{for(int i = 0;i < n;++i){for(int j = 0;j < m;++j){if(j) cout << ' ';cout << ans[i][j];}if(i < n) cout << endl;}
}inline void solve()
{cin >> n >> m;for(int i = 0;i < n;++i){for(int j = 0;j < m;++j){cin >> g[i][j];// 答案数组初始化ans[i][j] = -1;}}// 开始BFSBFS();// 输出答案PrintAns();
}int main()
{
//	freopen("a.txt", "r", stdin);___G;int _t = 1;
//	cin >> _t;while (_t--){solve();}return 0;
}

最后提交：