D.虫洞操纵者

前言：

本蒟蒻的第一篇题解，有什么写不好的地方欢迎大家私信评论，关于这篇题解其实也是不好意思写的，因为当时比赛感觉自己ac不出来就疯狂骗分去了（笑了），然后赛后翻了下通过的代码，发现有一个ac的代码解题思路非常清晰，看了一下然后自己又行了就试着按他的思路做了下，不出意外的就ac了。后来又翻了下题解发现D题的题解基本上都有点“又长又臭”的感觉（bushi狗头保命）（ort大佬勿喷qwq），只是本蒟蒻太菜了看不懂。发现竟然没有我看见的那篇的代码，感觉我看见的那篇代码量又短，思路又清晰，我怎么能忍心让它埋没，不分享给你们，看见没有佬来，那就献丑辣。（顺便记录一下嘻嘻）

解题思路：

很明显这是一道比较经典的BFS＋队列的板子题，只需要在移动过程中判断是否可以开个虫洞，穿越。（个人拙见）

上代码：

#include<bits/stdc++.h> // 万能头
#define ll long long
const int N = 2e6 + 10;
using namespace std;
ll dis[1110][1110];  // 位置（值为步数）
ll mp[1100][1100];// 地图
ll vis[1101][1110]; // 初始值为0，用来判断是否走过
ll dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
ll n;
 void  bfs()
 {
  queue<pair<ll,ll> >q; // 坐标
  q.push({1,1});
  vis[1][1]=1;  // 标记 
  while(!q.empty())
{
    int x=q.front().first;
    int y=q.front().second;
    q.pop();
    for(int i=0;i<4;i++)
    {
        int nx=x+dir[i][0];
        int ny=y+dir[i][1]; // 这里是加，下面是减，即类似穿越
        if(vis[nx][ny])continue; // 已走过，继续，节省时间
        if(mp[nx][ny]==1) // 碰见墙体
        {
            while(mp[nx-dir[i][0]][ny-dir[i][1]]==0)
            {
                nx-=dir[i][0]; // 向该方向移动，直到碰到另一个墙体
                ny-=dir[i][1]; // 个人感觉，这才是最难理解的地方但也是最关键的地方，处理的比较巧妙
            }
        }
        if(vis[nx][ny]) continue; //同上
            dis[nx][ny]=dis[x][y]+1; // 记录步数
        q.push({nx,ny});
        vis[nx][ny]=1;
    }
}
if(dis[n][n]==0)cout<<-1<<"\n"; // 即到达不了，无解
else
    cout<<dis[n][n]<<endl; // 步数       
}

void solve()
{
    cin>>n;
 for(int i=1;i<=n;i++)
  for(int j=1;j<=n;j++)  // 输入
    cin>>mp[i][j];
     for(int i=1;i<=n;i++)
     {
      mp[0][i]=1;
      mp[i][0]=1;  //  预处理周围一圈是墙
      mp[i][n+1]=1;
      mp[n+1][i]=1;
     }
      bfs();
 }  
 
 int main()
{
  ll t=1 ;
 //cin >> t;
 while (t--)
 {
     solve();
 }
 return 0;
}