rt
双端队列优化 dij ，re on #3 #21 #31

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int x,y,v;
};
int n,m;
char x;
bool flag[1050][1050]={};
vector<Node>b[1050][1050];
deque<Node>dij;
Node u;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>x;
            if(x=='\\'){
                b[i-1][j-1].push_back((Node){i,j,0});
                b[i][j].push_back((Node){i-1,j-1,0});
                b[i-1][j].push_back((Node){i,j-1,1});
                b[i][j-1].push_back((Node){i-1,j,1});
            }
            else{
                b[i-1][j-1].push_back((Node){i,j,1});
                b[i][j].push_back((Node){i-1,j-1,1});
                b[i-1][j].push_back((Node){i,j-1,0});
                b[i][j-1].push_back((Node){i-1,j,0});
            }
        }
    }
    dij.push_front({0,0,0});
    flag[0][0]=1;
    while(1){
        u=dij.front();
        dij.pop_front();
        flag[u.x][u.y]=1;
        if(u.x==n&&u.y==m){
            cout<<u.v;
            return 0;
        }
        for(int i=0;i<b[u.x][u.y].size();i++){
            if(flag[b[u.x][u.y][i].x][b[u.x][u.y][i].y])continue;
            if(b[u.x][u.y][i].v==0)dij.push_front((Node){b[u.x][u.y][i].x,b[u.x][u.y][i].y,b[u.x][u.y][i].v+u.v});
            else dij.push_back((Node){b[u.x][u.y][i].x,b[u.x][u.y][i].y,b[u.x][u.y][i].v+u.v});
        }
    }
    return 0;
}