record

求调QAQ

#include<bits/stdc++.h>
using namespace std;
const int N=5e2+10;
struct node{int x,y,p;};
int n,m,dx[5]={0,-1,1,1,-1},dy[5]={0,-1,1,-1,1},ans=1e9;
bool g[N][N],vis[N][N];
deque<node>q;
bool loc(node nod,int d)
{
    if(d==1)return g[nod.x-1][nod.y-1];
    if(d==2)return g[nod.x][nod.y];
    if(d==3)return g[nod.x][nod.y-1];
    if(d==4)return g[nod.x-1][nod.y];
}
void bfs()
{
    q.push_back({1,1,0});vis[1][1]=1;
    while(!q.empty())
    {
        node bot=q.back();q.pop_back();
        // printf("%d %d %d\n",bot.x,bot.y,bot.p);
        if(bot.x==n&&bot.y==m){ans=bot.p;return;}
        for(int i=1;i<=4;i++)
        {
            node top;top.p=bot.p;
            top.x=bot.x+dx[i];top.y=bot.y+dy[i];
            bool eg=loc(bot,i);
            if(!(eg&&i==4||eg&&i==3||!eg&&i==1||!eg&&i==2))top.p++;
            if(top.x<1||top.x>n||top.y<1||top.y>m||vis[top.x][top.y])continue;
            vis[top.x][top.y]=1;
            if(top.p>bot.p)q.push_front(top);
            else q.push_back(top);
        }
    }
    return;
}
signed main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            char ch;cin>>ch;
            if(ch=='/')g[i][j]=1;
            else if(ch=='\\')g[i][j]=0;
        }
    n++;m++;bfs();
    if(ans<=n*m)printf("%d\n",ans);
    else puts("NO SOLUTION");
    return 0;
}