【HDOJ】1180 诡异的楼梯

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 ;
}
上一篇:《C++primer》v5 第4章 表达式 读书笔记 习题答案


下一篇:(VS) TFS lost mapping suddenly.