NOI 题库 2753
2024-10-19 01:25:03
2753 走迷宫
- 描述
- 一个迷宫由R行C列格子组成,有的格子里有障碍物,不能走;有的格子是空地,可以走。
给定一个迷宫,求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走,不能斜着走。 - 输入
- 第一行是两个整数,R和C,代表迷宫的长和宽。( 1<= R,C <= 40)
接下来是R行,每行C个字符,代表整个迷宫。
空地格子用'.'表示,有障碍物的格子用'#'表示。
迷宫左上角和右下角都是'.'。 - 输出
- 输出从左上角走到右下角至少要经过多少步(即至少要经过多少个空地格子)。计算步数要包括起点和终点。
- 样例输入
-
5 5
..###
#....
#.#.#
#.#.#
#.#.. - 样例输出
-
9
#include "bits/stdc++.h" using namespace std;
const int maxN = ;
const int INF = ;
const int dx [ ] = { , - , , } ;
const int dy [ ] = { , , - , } ;
typedef long long QAQ ; int r , c , ans = INF ; char mp[ maxN ][ maxN ] ;
bool vis[ maxN ][ maxN ] ; void DFS ( const int xi , const int yi , const int step ) {
if ( mp[ xi ][ yi ] == '#' || step > ans ) return ;//当当前答案比已有答案差,不再继续搜索
if( xi == r && yi == c ) {
ans = min ( ans , step ) ;
return ;
}
for(int i = ; i < ; ++i ) {
int xx = xi + dx [ i ] ;
int yy = yi + dy [ i ] ;
if ( !vis[ xx ][ yy ] && mp[ xx ][ yy ] == '.' ) { vis[ xx ][ yy ] = true ;
DFS( xx , yy , step + ) ;
vis[ xx ][ yy ] = false ;
}
}
} void Init ( ){
for ( int i= ; i<=r+ ; ++i )
for ( int j= ; j<=c+ ; ++j )
if ( i== || i == r+ || j== || j== c+ ) mp[ i ][ j ] = '#' ;
} int main ( ) {
scanf ( "%d%d" , &r , &c ) ;
Init ( );
getchar ( ) ;
for ( int i= ; i<=r ; ++i ){
for ( int j= ; j<=c ; ++j ) {
mp[ i ][ j ] = getchar ( ) ;
}
getchar ( ) ;
} vis[ ][ ] = true;
DFS ( , , ) ;
cout << ans << endl ;
return ;
}2016-10-18 18:20:22
(完)
最新文章
- Swift的关键字
- ENode通信层性能测试结果
- js的高级知识---词法分析
- css优先级和层叠
- Android开发EditText属性
- form表单只提交数据而不进行页面跳转的解决方案
- HDU 3496 Watch The Movie(看电影)
- I.MX6 Linux、Jni ioctl 差异
- 用MySQL log调试程序
- 使用javascript获取gridview中的textbox值
- 网络知识汇总(2) - Linux下如何修改ip地址
- CORS(跨域资源共享)
- 201521123107 《Java程序设计》第6周学习总结
- 解析Visual C# 7.2中的private protected访问修饰符
- spring-boot-2.0.3源码篇 - pageHelper分页,绝对有值得你看的地方
- vue项目做seo优化(prerender-spa-plugin vue-meta-info)
- macOS 安装 ctags
- 【Math for ML】解析几何(Analytic Geometry)
- 用Java画简单验证码
- 命令模式(head first 设计模式5)