ACWING 844. 走迷宫
2024-10-18 22:35:25
地址 https://www.acwing.com/problem/content/description/846/
给定一个n*m的二维整数数组,用来表示一个迷宫,数组中只包含0或1,其中0表示可以走的路,1表示不可通过的墙壁。
最初,有一个人位于左上角(1, 1)处,已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问,该人从左上角移动至右下角(n, m)处,至少需要移动多少次。
数据保证(1, 1)处和(n, m)处的数字为0,且一定至少存在一条通路。
输入格式
第一行包含两个整数n和m。
接下来n行,每行包含m个整数(0或1),表示完整的二维数组迷宫。
输出格式
输出一个整数,表示从左上角移动至右下角的最少移动次数。
数据范围
1≤n,m≤100
输入样例: 输出样例:
解法
BFS搜索 不采取DFS是因为BFS可以获取最短路径
#include <iostream>
#include <algorithm>
#include <queue> using namespace std; const int N = ; int g[N][N];
int dis[N][N]; int n, m; typedef pair<int, int> PII; queue<PII> que; int rowadd[] = { ,-,, };
int coladd[] = { ,,,- }; void bfs(int row, int col)
{
while (!que.empty())
{
PII xy = que.front();
que.pop(); for (int i = ; i < ; i++) {
int nextrow = xy.first + rowadd[i];
int nextcol = xy.second + coladd[i]; if (nextrow == n && nextcol == m) {
//达到终点
cout << (dis[xy.first][xy.second] + ) << endl;
return;
} if (nextrow >= && nextrow <= n && nextcol >= && nextcol <= m)
{
if (g[nextrow][nextcol] == ) {
g[nextrow][nextcol] = ; dis[nextrow][nextcol] = dis[xy.first][xy.second] + ;
que.push({ nextrow,nextcol });
}
}
} } } int main()
{
cin >> n >> m;
for (int i = ; i <= n; i++) {
for (int j = ; j <= m; j++) {
cin >> g[i][j];
}
} que.push({ , });
g[][] = ;
dis[][] = ;
bfs(, ); return ;
}
最新文章
- 给jquery-validation插件添加控件的验证回调方法
- Keil>; 编译器特有的功能 >; 关键字和运算符 >; __weak
- Hibernate 系列 07 - Hibernate中Java对象的三种状态
- 设计模式(Design Pattern)系列之.NET专题
- cocoapods 升级到最新beta 版
- Git学习笔记(7)——多人协作
- Java 控制线程
- Java生成动态GIF图片
- 如何优化cocos2d程序的内存使用和程序大小:第一部分
- 用c#开发微信(1)服务号的服务器配置和企业号的回调模式 - url接入 (源码下载)
- MySQL扩展功能 - 重复插入
- nginx使用keepalived实现高可用
- iOS集成微信支付
- Hper-V卸载
- [Shell]sed命令在MAC和Linux下的不同使用方式
- CF1121C 模拟
- NOI2017 游记
- java基础学习之抽象类
- 表单:提交验证,及blur事件验证
- SQL Server 数据库备份失败解决方法