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