Codeforces Round #354 (Div. 2) D. Theseus and labyrinth

题目链接:

http://codeforces.com/contest/676/problem/D

题意:

如果两个相邻的格子都有对应朝向的门,则可以从一个格子到另一个格子,给你初始坐标xt,yt,终点坐标xm,ym,现在你可以选择在原地把地图上所有格子顺时针旋转90度;或者往上下左右走一格,问走到终点的最短路。

题解:

三维的bfs最短路,就是写起来比较麻烦。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<utility>
using namespace std; const int maxn = ;
int n, m; char str[][maxn][maxn]; char mp[],dir[][];
void get_mp(){
memset(mp, , sizeof(mp));
mp['+'] = '+';
mp['-'] = '|';
mp['|'] = '-';
mp['^'] = '>';
mp['>'] = 'v';
mp['v'] = '<';
mp['<'] = '^';
mp['L'] = 'U';
mp['U'] = 'R';
mp['R'] = 'D';
mp['D'] = 'L';
mp['*'] = '*'; memset(dir, , sizeof(dir));
dir['+'][] = dir['+'][] = dir['+'][] = dir['+'][] = ;
dir['-'][]=dir['-'][]=;
dir['|'][]=dir['|'][]=;
dir['^'][]=;
dir['>'][]=;
dir['v'][]=;
dir['<'][]=;
dir['L'][]=dir['L'][]=dir['L'][]=;
dir['U'][]=dir['U'][]=dir['U'][]=;
dir['R'][]=dir['R'][]=dir['R'][]=;
dir['D'][] = dir['D'][] = dir['D'][] = ;
} struct Node {
int s, x, y;
Node(int s, int x, int y) :s(s), x(x), y(y) {}
Node() {}
}; int xt, yt, xm, ym;
int d[][maxn][maxn];
int vis[][maxn][maxn];
int bfs() {
memset(d, 0x3f, sizeof(d));
memset(vis, , sizeof(vis));
d[][xt][yt] = ;
queue<Node> Q;
Q.push(Node(, xt, yt)); vis[][xt][yt] = ;
while (!Q.empty()) {
Node nd = Q.front(); Q.pop();
int s = nd.s, x = nd.x, y = nd.y;
if (x == xm&&y == ym) return d[s][x][y];
int ss, xx, yy;
ss = (s + ) % , xx = x, yy = y;
if (!vis[ss][xx][yy]) {
d[ss][xx][yy] = d[s][x][y] + ;
Q.push(Node(ss, xx, yy));
vis[ss][xx][yy] = ;
}
ss = s, xx = x - , yy = y;
if (!vis[ss][xx][yy]&&xx>=&&dir[str[ss][xx][yy]][]&&dir[str[s][x][y]][]) {
d[ss][xx][yy] = d[s][x][y] + ;
Q.push(Node(ss, xx, yy));
vis[ss][xx][yy] = ;
}
ss = s, xx = x + , yy = y;
if (!vis[ss][xx][yy] && xx <=n && dir[str[ss][xx][yy]][] && dir[str[s][x][y]][]) {
d[ss][xx][yy] = d[s][x][y] + ;
Q.push(Node(ss, xx, yy));
vis[ss][xx][yy] = ;
}
ss = s, xx = x, yy = y-;
if (!vis[ss][xx][yy] && yy >= && dir[str[ss][xx][yy]][] && dir[str[s][x][y]][]) {
d[ss][xx][yy] = d[s][x][y] + ;
Q.push(Node(ss, xx, yy));
vis[ss][xx][yy] = ;
}
ss = s, xx = x, yy = y + ;
if (!vis[ss][xx][yy] && yy <= m && dir[str[ss][xx][yy]][] && dir[str[s][x][y]][]) {
d[ss][xx][yy] = d[s][x][y] + ;
Q.push(Node(ss, xx, yy));
vis[ss][xx][yy] = ;
}
}
return -;
} int main() {
get_mp();
while (scanf("%d%d", &n, &m) == && n) {
for (int i = ; i <= n; i++) scanf("%s", str[][i]+);
for (int i = ; i <= ; i++) {
for (int j = ; j <= n; j++) {
for (int k = ; k <= m; k++) {
str[i][j][k] = mp[str[i - ][j][k]];
}
}
}
scanf("%d%d%d%d", &xt, &yt, &xm, &ym);
printf("%d\n", bfs());
}
return ;
}
上一篇:Codeforces Round #354 (Div. 2)-B


下一篇:Codeforces Round #354 (Div. 2)-A