bfs+优先队列。wa了N次,才发现可以停留等待楼梯变换方向。

 #include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std; #define MAXNUM 55 typedef struct node_st {
int x, y, t;
node_st() {}
node_st(int xx, int yy, int tt) {
x = xx; y = yy; t = tt;
}
friend bool operator < (node_st a, node_st b) {
return a.t > b.t;
}
} node_st; char map[MAXNUM][MAXNUM];
char visit[MAXNUM][MAXNUM];
int n, m;
int begx, begy, endx, endy;
int direct[][] = {{,},{-,},{,},{,-}}; int bfs(int begx, int begy) {
priority_queue<node_st> que;
node_st node;
int i, x, y, nx, ny, t; que.push(node_st(begx, begy, ));
memset(visit, , sizeof(visit));
visit[begx][begy] = ; while ( !que.empty() ) {
node = que.top();
if (map[node.x][node.y] == 'T') {
return node.t;
}
que.pop();
for (i=; i<; ++i) {
x = node.x + direct[i][];
y = node.y + direct[i][];
if (x< || x>=n || y< || y>=m)
continue;
if (visit[x][y] || map[x][y] == '*')
continue;
if (map[x][y] == '.' || map[x][y]=='T') {
que.push(node_st(x,y,node.t+));
visit[x][y] = ;
continue;
}
if (map[x][y]=='|' || map[x][y]=='-') {
nx = x + direct[i][];
ny = y + direct[i][];
t = node.t + ;
if (nx< || nx>=n || ny< || ny>=m)
continue;
if (visit[nx][ny] || map[nx][ny]=='*')
continue;
if ( ((map[x][y]=='|') && ((node.t&)==) && (i==||i==)) ||
((map[x][y]=='|') && ((node.t&)!=) && (i==||i==)) ||
((map[x][y]=='-') && ((node.t&)==) && (i==||i==)) ||
((map[x][y]=='-') && ((node.t&)!=) && (i==||i==)) )
++t;
visit[nx][ny] = ;
que.push(node_st(nx, ny, t));
}
}
} return -;
} int main() {
int i, j; while (scanf("%d %d%*c",&n,&m) != EOF) {
for (i=; i<n; ++i) {
scanf("%s", map[i]);
for (j=; j<m; ++j) {
if (map[i][j] == 'S') {
begx = i;
begy = j;
}
}
}
i = bfs(begx, begy);
printf("%d\n", i);
} return ;
}

最新文章

  1. PHP使用内置函数生成图片的方法详解
  2. Java中this、super用法
  3. 慕课网-安卓工程师初养成-3-8 Java中的条件运算符
  4. python练习程序(c100经典例18)
  5. HTML+CSS实例——漂亮的查询部件(一)
  6. 1523. K-inversions(K逆序对)
  7. iOS cell自动换行
  8. javabean、DTO、VO
  9. (原)opencv直线拟合fitLine
  10. DOS下导入导出MySQL备份
  11. ABP Zero 单部署,单数据库,多租户架构
  12. iconfont 字库入门到精通
  13. js的onscroll、scrollTop、scrollHeight及window.scroll等方法
  14. JDK源码及其他框架源码解析随笔地址导航
  15. JRE与JDK简介
  16. macOS HomeBrew更换源 brew常用命令说明
  17. 第15课 右值引用(2)_std::move和移动语义
  18. C# DataTbale详细操作
  19. 给构造函数(constructor)创建对象(object)
  20. hive-hbase-handler方式导入hive表数据到hbase表中

热门文章

  1. Asp.Net Core简单整理
  2. iOS 开发中的单例
  3. UIView的frame和bounds区别
  4. 类型与通用语言运行时:System.Object
  5. Myeclipse下不用dom4j等解析xml文档
  6. Cocos2d-x 3.0 cocostudio骨骼动画的动态换肤
  7. 获取元素样式 currentStyle 和 getcomputedStyle
  8. Oracle的硬解析和软解析
  9. ubuntu zend-eclipse-php debugger调试
  10. H5小内容(四)