#include #pragma GCC optimize("Ofast") using namespace std; using std::cout; using std::cin; using std::endl; using ll=long long; using ld=long double; ll I=1167167167167167167; ll Q=1e9+7; #define rep(i,a) for (ll i=0;i using _pq = priority_queue, greater>; template ll LB(vector &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();} template ll UB(vector &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();} template bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}else return 0;} template bool chmax(T &a,const T &b){if(a void So(vector &v) {sort(v.begin(),v.end());} template void Sore(vector &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});} template void print_tate(vector &v) {rep(i,v.size()) cout<>H>>W; int s1,s2,g1,g2; cin>>s1>>s2>>g1>>g2; s1--,s2--,g1--,g2--; int s=s1*W+s2,g=g1*W+g2; int p[H][W]; int dp[H][W][6]; rep(i,H) rep(j,W){ char a; cin>>a; if(a=='.') p[i][j]=1; else p[i][j]=0; rep(k,6) dp[i][j][k]=Q; } dp[s1][s2][0]=0; queue> q; q.push({s1,s2,0}); vector>> diff={ {{1,0,1},{-1,0,3},{0,1,4},{0,-1,2}}, {{1,0,5},{-1,0,0},{0,1,1},{0,-1,1}}, {{1,0,2},{-1,0,2},{0,1,0},{0,-1,5}}, {{1,0,0},{-1,0,5},{0,1,3},{0,-1,3}}, {{1,0,4},{-1,0,4},{0,1,5},{0,-1,0}}, {{1,0,3},{-1,0,1},{0,1,2},{0,-1,4}} }; while (!q.empty()) { int x,y,t; tie(x,y,t)=q.front(); int L=dp[x][y][t]; L++; q.pop(); rep(i,4){ int a,b,c; tie(a,b,c)=diff[t][i]; int u=a+x,v=b+y; if(u==-1||u==H||v==-1||v==W||p[u][v]==0) continue; if(dp[u][v][c]==Q){ dp[u][v][c]=L; q.push({u,v,c}); } } } /*rep(i,H){ rep(j,W) cout<