题目：
http://codeforces.com/problemset/problem/676/D
code:
#include <stdio.h> #define MAXN 1001 #define LEFT 0 #define TOP 1 #define RIGHT 2 #define BOTTOM 3 struct block{ //left,top,right,bottom int doors[4]; int doors_num; int rotats; int minutes; }; struct block labyrinth[MAXN][MAXN]; char visited[MAXN][MAXN]; struct node{ int x; int y; }; int top; struct node path[MAXN*MAXN]; int N,M; int xt,yt,xm,ym; int min_minutes = 0x0FFFFFFF; void init_doors(int x,int y,char c) { int i; for (i=0;i<4;i++) { labyrinth[x][y].doors[i] = 0; } labyrinth[x][y].doors_num =0; labyrinth[x][y].rotats = 0; labyrinth[x][y].minutes = 0x0FFFFFFF; switch(c) { case '+': for (i=0;i<4;i++) { labyrinth[x][y].doors[i] = 1; } labyrinth[x][y].doors_num = 4; labyrinth[x][y].rotats = 0; break; case '-': labyrinth[x][y].doors[LEFT] = 1; labyrinth[x][y].doors[RIGHT] =1; labyrinth[x][y].doors_num = 2; break; case '|': labyrinth[x][y].doors[TOP] = 1; labyrinth[x][y].doors[BOTTOM] =1; labyrinth[x][y].doors_num = 2; break; case '^': labyrinth[x][y].doors[TOP] = 1; labyrinth[x][y].doors_num = 1; break; case '>': labyrinth[x][y].doors[RIGHT] = 1; labyrinth[x][y].doors_num = 1; break; case '<': labyrinth[x][y].doors[LEFT] = 1; labyrinth[x][y].doors_num = 1; break; case 'V': labyrinth[x][y].doors[BOTTOM] = 1; labyrinth[x][y].doors_num = 1; labyrinth[x][y].rotats = 0; break; case 'L': labyrinth[x][y].doors[TOP] = 1; labyrinth[x][y].doors[BOTTOM] =1; labyrinth[x][y].doors[RIGHT] = 1; labyrinth[x][y].doors_num =3; labyrinth[x][y].rotats = 0; break; case 'R': labyrinth[x][y].doors[TOP] = 1; labyrinth[x][y].doors[BOTTOM] =1; labyrinth[x][y].doors[LEFT] = 1; labyrinth[x][y].doors_num = 3; labyrinth[x][y].rotats = 0; break; case 'U': labyrinth[x][y].doors[RIGHT] = 1; labyrinth[x][y].doors[BOTTOM] =1; labyrinth[x][y].doors[LEFT] = 1; labyrinth[x][y].doors_num = 3; break; case 'D': labyrinth[x][y].doors[TOP] = 1; labyrinth[x][y].doors[RIGHT] =1; labyrinth[x][y].doors[LEFT] = 1; labyrinth[x][y].doors_num = 3; break; } } void push(int i,int j) { top++; path[top].x = i; path[top].y = j; } struct node pop() { top--; return path[top +1]; } int get_door(int x,int y,int direction,int roates) { int t = roates % 4; int index = direction - t; if (index < 0) { index += 4; } return labyrinth[x][y].doors[index]; } void process_state(int x,int y,int cur_rotates,int cur_time) { int dir_y[4] = {-1,0,1,0}; int dir_x[4] = { 0,-1,0,1}; int i,nx,ny; for (i=0;i<4;i++) { nx = x+dir_x[i]; ny = y+dir_y[i]; if (nx<1 || nx >N) { continue; } if (ny<1 || ny>M) { continue; } if (get_door(x,y,i,cur_rotates)&& get_door(nx,ny,(i+2)%4,cur_rotates)) { if (!visited[nx][ny]) { visited[nx][ny] =1; labyrinth[nx][ny].minutes = cur_time+1; labyrinth[nx][ny].rotats = cur_rotates; if (nx == xm && ny == ym) { if (min_minutes > cur_time+1) { min_minutes = cur_time+1; } }else { push(nx,ny); } }else { if (labyrinth[nx][ny].minutes >cur_time+1 ) { labyrinth[nx][ny].minutes = cur_time+1; labyrinth[nx][ny].rotats = cur_rotates; push(nx,ny); } } } } } int bfs() { int x,y,cur_rotates,i,nx,ny,t,cur_time; struct node cur; top = -1; push(xt,yt); labyrinth[xt][yt].minutes = 0; visited[xt][yt] =1; while(top!= -1) { cur = pop(); //left x = cur.x; y = cur.y; cur_rotates = labyrinth[x][y].rotats; cur_time = labyrinth[x][y].minutes; t = 0; while(t < 4) { if (cur_time + t < min_minutes) { process_state(x,y,cur_rotates+t,cur_time+t); } t++; } } return labyrinth[xm][ym].minutes; } int main() { int i,j; char str[MAXN];
scanf("%d %d",&N,&M); for (i=1;i<=N;i++) { scanf("%s ",str); for (j=1;j<=M;j++) { init_doors(i,j,str[j-1]); visited[i][j] = 0; } } scanf("%d %d",&xt,&yt); scanf("%d %d",&xm,&ym); //check same logcation if (xt == xm && yt == ym) { printf("0"); return 0; } //dfs(xt,yt,0); bfs(); if(min_minutes == 0x0FFFFFFF) printf("-1"); else printf("%d",min_minutes); return 0; }