D题

暴力bfs遍历找最短路

唯一的变化是，碰到墙后要for循环反向走到对面的墙前即可，遇到终点要提前退出

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int,int> PII;
int n,g[1005][1005],step[1005][1005];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

int bfs()
{
    queue<pair<int,int>> q;
    q.push({1,1});
    step[1][1]=1;
    
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        if(t.x==n && t.y==n)return step[t.x][t.y]-1;
        
        for(int i=0;i<4;i++)
        {
            int nx=t.x+dx[i],ny=t.y+dy[i];

            if(nx<1 || nx>n || ny<1 || ny>n || g[nx][ny]==1)
            {
                if(i==0)for(int j=t.x;j<=n+1;j++)if(g[j][t.y]==1 || j==n+1){nx=j-1;break;}
                if(i==1)for(int j=t.y;j>=0;j--)if(g[t.x][j]==1 || j==0){ny=j+1;break;}
                if(i==2)for(int j=t.x;j>=0;j--)if(g[j][t.y]==1 || j==0){nx=j+1;break;}
                if(i==3)for(int j=t.y;j<=n+1;j++)if(g[t.x][j]==1 || j==n+1){ny=j-1;break;}
            }
            
            if(step[nx][ny]==0)
            {
                step[nx][ny]=step[t.x][t.y]+1;
                q.push({nx,ny});
            }
        }
    }
    return -1;
}

void solved()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)cin>>g[i][j];
    cout<<bfs();
}

int main()
{
    solved();
    return 0;
}