https://ac.nowcoder.com/acm/contest/86387/F
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<unordered_set>
#include<unordered_map>
using namespace std;
#define ll long long
#define all(x) (x).begin(),(x).end()
const int N=1e3+10;
int n,m;
char dt[N][N];
int dx[]={0,-1,1,0};
int dy[]={-1,0,0,1};
int dis[N][N],vis[N][N][5];
struct ss{
int x,y,s,no;
bool operator<(const struct ss& a)const{
return this->s>a.s;
}
};
bool check(int x,int y){
if(x>=1 && x<=n && y>=1 && y<=m) return true;
return false;
}
void dijkstra(){
memset(dis,0x3f,sizeof dis);
priority_queue<ss> pq;
dis[1][1]=0,pq.push({1,1,0,-1});
while(!pq.empty()){
auto t=pq.top(); pq.pop();
int x=t.x,y=t.y;
// -1表示上下左右都可以移动
if(vis[x][y][(t.no+5)%5]) continue;
vis[x][y][(t.no+5)%5]=1;
for(int i=0;i<4;i++){
if(i==t.no) continue;
int xx=x+dx[i];
int yy=y+dy[i];
if(!check(xx,yy)) continue;
if(dt[xx][yy]=='.'){
if(dis[x][y]+1<dis[xx][yy]){
dis[xx][yy]=dis[x][y]+1;
pq.push({xx,yy,dis[xx][yy],t.no});
}
}
else{
if(t.no!=-1) continue;
if(dis[x][y]+1<dis[xx][yy]){
dis[xx][yy]=dis[x][y]+1;
for(int j=0;j<4;j++)
if(i!=j) pq.push({xx,yy,dis[xx][yy],j});
}
}
}
}
cout<<(dis[n][m]==0x3f3f3f3f?-1:dis[n][m]);
}
int main(){
ios::sync_with_stdio(false),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>dt[i][j];
dijkstra();
return 0;
}