企业网站管理系统站长之家,图片网站模板,网站后台上传图片做难吗,庆阳定制网站题目#xff1a;
样例#xff1a; 输入 3 3
0 0 0
1 0 0
0 1 0 输出 0 1 2
-1 2 3
-1 -1 4 思路#xff1a; 单纯的 BFS 迷宫问题#xff0c;只是标记一下每个点的 step#xff0c;注意初始化答案数组都为 -1.
代码详解如下#xff1a;
#include iostream
#…题目
样例
输入 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 pairint,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;queuePIIq;// 存储起点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;
}
最后提交
