http://codeforces.com/contest/676/problem/D
题目大意：
勇者去迷宫杀恶龙。迷宫是有n*m的方格子组成的。迷宫上有各种记号，这些记号表达着能走的方向。当且仅当两个房间的记号是相互联通的，才能走过去。
我们有如下选择，最直白的一种就是直接走到另外一个格子上去（当然格子得相互连通），第二种操作就是顺时针旋转所有的格子（格子的位置保持不变）。
问，勇者要多久才能走到恶龙所在的地方。
思路：
表示这道题真心不会。。。下面的这个代码也是参考了别人的吧。。。换成我的话for的循环里面肯定不会写成f*3+i之类的（虽然这个到现在还没有弄明白）
我们用结构体保存当前的位置，旋转的次数和行走的距离。然后我们每次对一个当前的格子进行两种操作
①瞬时间旋转操作（每次都旋转1，反正最后肯定会遍历到4的）
②就是枚举上下左右，看看是否能走过去。
然后就OK了
//看看会不会爆int!
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define all(a) a.begin(), a.end() const int maxn = ;
bool vis[maxn][maxn][];
int n, m;
struct point{
int x, y;
int f, d;
point(int xx = , int yy = , int ff = , int dd = ){
x = xx, y = yy, f = ff, d = dd;
}
}p[maxn][maxn]; char atlas[maxn][maxn];
int xt, yt, xm, ym;
/*
int dx[] = {0, 0, -1, 1};//上下左右
int dy[] = {-1, 1, 0, 0};
*/
int dx[] = {-, , , };//左下右上
int dy[] = {, , , -}; bool check(char ch, int dir){
if (dir == ) return ch == '+' || ch == '|' || ch == '^' || ch == 'L' || ch == 'R' || ch == 'D';
else if (dir == ) return ch == '+' || ch == '-' || ch == '>' || ch == 'L' || ch == 'U' || ch == 'D';
else if (dir == ) return ch == '+' || ch == '|' || ch == 'v' || ch == 'L' || ch == 'R' || ch == 'U';
else return ch == '+' || ch == '-' || ch == '<' || ch == 'R' || ch == 'U' || ch == 'D';
return ;
} int bfs(){
queue <point> que;
vis[xt][yt][] = ;
que.push(point(xt, yt, , ));
while (!que.empty()){
point q = que.front();
que.pop();
int x = q.x, y = q.y;
int f = q.f, d = q.d;
if (x == xm && y == ym) return d;
if (!vis[x][y][(f + ) % ]){
vis[x][y][(f + ) % ] = true;
que.push(point(x, y, (f + ) % , d + ));
}
for (int i = ; i < ; i++){
int nx = x + dx[i], ny = y + dy[i];
if (nx <= || ny <= || nx > n || ny > m) continue;
if (atlas[nx][ny] == '*' || vis[nx][ny][f]) continue;
if (!check(atlas[x][y], (f * + i) % )) continue;//我们要选择的是和上面相反的方向
if (!check(atlas[nx][ny], (f * + i + ) % )) continue;
que.push(point(nx, ny, f, d + ));
vis[nx][ny][f % ] = true;
}
}
return -;
} int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++){
scanf("%s", atlas[i] + );
}
scanf("%d%d", &xt, &yt);
scanf("%d%d", &xm, &ym);
int ans = bfs();
printf("%d\n", ans);
return ;
}
/*
_ooOoo_
o8888888o
88" . "88
(| -_- |)
O\ = /O
____/`---'\____
.' \\| |// `.
/ \\||| : |||// \
/ _||||| -:- |||||- \
| | \\\ - /// | |
| \_| ''\---/'' | |
\ .-\__ `-` ___/-. /
___`. .' /--.--\ `. . __
."" '< `.___\_<|>_/___.' >'"".
| | : `- \`.;`\ _ /`;.`/ - ` : | |
\ \ `-. \_ __\ /__ _/ .-` / /
======`-.____`-.___\_____/___.-`____.-'======
`=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
佛祖保佑 永无BUG
*/