https://www.luogu.com.cn/problem/P1126

题意：2 * 2 的矩阵块从起点到终点，有 向左转，向右转，前进一步，前进2步，前进三步 5种操作。每个操作花费 1 秒。 问最少时间？

直接搜索会超时的，，
要注意的是，每个位置的状态要把方向算进去。但是向前走的时候不用考虑方向，只要可以通过即可。 走多步的时候，要一个一个判断，可能中间有墙。
双向 BFS 的时候，相遇的时候两个方向需要特别处理，因为转向也有代价。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sf(n) scanf("%d",&n)
#define pf(n) printf("%d",n)
#define pfc(c) printf(c)
#define fi(i,s,t) for(int i=s;i<t;i++)
#define fd(s,t) for(int i=s-1;i>=t;i--)
#define mem(a,c) memset(a,c,sizeof(a))
const int INF=0x3f3f3f3f;
const int MAX=55;
int n,m,a[MAX][MAX],vis[MAX][MAX][4],vis2[MAX][MAX],len[MAX][MAX][4],
   sx,sy,fx,fy,f,ans=INF,aw[4][2]={-1,0,0,1,1,0,0,-1},
   awr[4]={2,3,0,1},flag=0; //flag for end point
char tf;
struct node{
	int x,y;
	int f;
	node(int _x,int _y,int _f){
		x=_x;y=_y;f=_f;
	}
};
bool judge(int x,int y){
	if(x<1 || x> n-1 || y<1 || y> m-1) return false;
	if(a[x][y] ||a[x][y+1] ||a[x+1][y] ||a[x+1][y+1]) return false;
	return true;
}
bool judge2(int x,int y,int f,int steps){// steps along f
	int tx,ty;
	fi(i,0,steps){
		tx= x + aw[f][0];
		ty= y + aw[f][1];
		if(!judge(tx,ty)) return false;
		x=tx;y=ty;
	}
	return true;
}
queue<node>q;
queue<node>h;
int bfs(node s,node r){
	mem(vis,0);
	mem(vis2,0);
	if(s.x==r.x && s.y==r.y) return 0;
	q.push(s);
	vis[s.x][s.y][s.f]=1;
	fi(i,0,4){
		h.push(node(r.x,r.y,i)); 
		vis[r.x][r.y][i]=1;
		len[r.x][r.y][i]=0;
	}
	vis2[s.x][s.y]=1;
	vis2[r.x][r.y]=2;
	while(!q.empty() || !h.empty()){
		if(!q.empty()){
			node t= q.front();
			q.pop();
			fi(i,1,3+1){
				if(judge2(t.x,t.y,t.f,i)){
					int tx=t.x+aw[t.f][0],ty=t.y+aw[t.f][1];
					fi(j,1,i){
						tx = tx + aw[t.f][0];
						ty = ty + aw[t.f][1];
					}
					if(vis2[tx][ty]==0){
						if(len[tx][ty][t.f]>len[t.x][t.y][t.f] + 1 || len[tx][ty][t.f]==0 )
							len[tx][ty][t.f]=len[t.x][t.y][t.f] + 1;
						vis[tx][ty][t.f]=1;
						vis2[tx][ty]=1;
						q.push(node(tx,ty,t.f));
					}else if(vis2[tx][ty]==2){
						int _min=INF;
						fi(j,0,4){
							if(len[tx][ty][j]){
								int tmp;
								if(t.f==awr[j]) tmp=0;
								else if((t.f - 1 +4)%4 == awr[j] ||(t.f + 1 +4)%4 == awr[j]) tmp=1;
								else tmp=2;
								if(_min > len[tx][ty][j] + len[t.x][t.y][t.f]+1 + tmp)
									_min=len[tx][ty][j] + len[t.x][t.y][t.f] +1+ tmp;
							}
						}
						return _min;
					}
				}
			}
			if(!vis[t.x][t.y][(t.f-1+4)%4]){
				int k=(t.f-1+4)%4;
				q.push(node(t.x,t.y,k)); //left
				vis[t.x][t.y][k]=1;
				if(len[t.x][t.y][k]>len[t.x][t.y][t.f] + 1 || len[t.x][t.y][k]==0)
					len[t.x][t.y][k] = len[t.x][t.y][t.f] + 1;
			}
			if(!vis[t.x][t.y][(t.f+1+4)%4]){
				int k=(t.f+1+4)%4;
				q.push(node(t.x,t.y,k)); //right
				vis[t.x][t.y][k]=1;
				if(len[t.x][t.y][k]>len[t.x][t.y][t.f] + 1 || len[t.x][t.y][k]==0 )
					len[t.x][t.y][k] = len[t.x][t.y][t.f] + 1;
			}
		}
		if(!h.empty()){
			node t= h.front();
			h.pop();
			fi(i,1,3+1){
				if(judge2(t.x,t.y,t.f,i)){
					int tx=t.x+aw[t.f][0],ty=t.y+aw[t.f][1];
					fi(j,1,i){
						tx = tx + aw[t.f][0];
						ty = ty + aw[t.f][1];
					}
					if(vis2[tx][ty]==0){
						if(len[tx][ty][t.f]>len[t.x][t.y][t.f] + 1 || len[tx][ty][t.f]==0 )
							len[tx][ty][t.f]=len[t.x][t.y][t.f] + 1;
						vis[tx][ty][t.f]=1;
						vis2[tx][ty]=2;
						h.push(node(tx,ty,t.f));
					}else if(vis2[tx][ty]==1){
						int _min=INF;
						fi(j,0,4){
							if(len[tx][ty][j]){
								int tmp;
								if(t.f==awr[j]) tmp=0;
								else if((t.f - 1 +4)%4 == awr[j] ||(t.f + 1 +4)%4 == awr[j]) tmp=1;
								else tmp=2;
								if(_min > len[tx][ty][j] + len[t.x][t.y][t.f] + 1+tmp)
									_min=len[tx][ty][j] + len[t.x][t.y][t.f]+1+ tmp;
							}
						}
						return _min;
					}
				}
			}
			if(!vis[t.x][t.y][(t.f-1+4)%4]){
				int k=(t.f-1+4)%4;
				h.push(node(t.x,t.y,k)); //left
				vis[t.x][t.y][k]=1;
				if(len[t.x][t.y][k]>len[t.x][t.y][t.f] + 1 || len[t.x][t.y][k]==0)
					len[t.x][t.y][k] = len[t.x][t.y][t.f] + 1;
			}
			if(!vis[t.x][t.y][(t.f+1+4)%4]){
				int k=(t.f+1+4)%4;
				h.push(node(t.x,t.y,k)); //right
				vis[t.x][t.y][k]=1;
				if(len[t.x][t.y][k]>len[t.x][t.y][t.f] + 1 || len[t.x][t.y][k]==0 )
					len[t.x][t.y][k] = len[t.x][t.y][t.f] + 1;
			}
		}
	}
	return -1;
}
int main(){
//	freopen("in","r",stdin);
	sf(n);sf(m);
	fi(i,1,n+1)
		fi(j,1,m+1)
			sf(a[i][j]);
	sf(sx);sf(sy);sf(fx);sf(fy);
	getchar();
	tf = getchar() ;
	switch(tf){
		case 'N' : f=0 ; break;
		case 'E' : f=1 ; break;
		case 'S' : f=2 ; break;
		case 'W' : f=3 ; break;
	}
	pf(bfs(node(sx,sy,f),node(fx,fy,0)) );//-1 all aw
	return 0;
}