[ABC246E] Bishop 2 题解

· · 题解

本题就是个裸的广搜，但是有了些数学的味道。

首先我们来判断肯定无解的情况：

b..
..*
...

像上面的这种情况（b 代表象，* 代表目的地），是肯定无法走到的（如果你有学过国际象棋，就知道这是显然的）——因为象只能走斜线，所以 x 和 y 坐标的奇偶性关系（相同或不同）不会改变。

这里特判一下，如果不满足条件就输出 -1。

if((abs(s.x-s.y)&1)!=(abs(e.x-e.y)&1)){
  cout<<"-1\n"; return 0;
}

于是我们就可以开始广搜。首先我们定义一个结构体，表示象目前的一个状态：

struct node{
  int x,y,step;
  // x 坐标，y 坐标和当前步数
}s,e,xx;

用一个数组表示每个点是否有障碍物。但是，本数组不止需要 0 和 1，还需要一个 2 的标记。因为，可能出现如下的情况。

b...
.r..
..*.

因为，如果我们把已经走过的点和障碍物混为一谈，那么上面的就会误判（用 b 表示象，r 代表已经走过的点，* 表示目的地）——程序会把那个 r 当成障碍物，直接就返回了，目的地就无法走到。

这样，我们用 0 标记没走过且可走的点，1 标记障碍物，2 标记已经走过的点即可。

枚举每个方向走的步数，如果遇到障碍物就 break（优化）。

这样时间复杂度是 O(n^3) 的，但是常数特别小，如果你还嫌慢可以加上 -Ofast 优化。可以在 6\mathrm{s} 的时限内随便通过。

放代码：

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
int a[1501][1501];
const int dx[4]={1,1,-1,-1},dy[4]={1,-1,1,-1};
struct node{int x,y,step;}s,e,xx;
queue<node> q;
int main(){
  ios::sync_with_stdio(false);
  int n; cin>>n>>s.x>>s.y>>e.x>>e.y;
  if((abs(s.x-s.y)&1)!=(abs(e.x-e.y)&1))
    cout<<"-1\n",exit(0); // 特判
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++){
      char c; cin>>c;
      if(c=='.')a[i][j]=0;
      else a[i][j]=1; // 障碍物
    }
  s.step=0,q.emplace(s);
  while(!q.empty()){
    node t=q.front(); q.pop();
    for(int i=0;i<4;i++){
      for(int j=1;j<n;j++){
        xx.x=t.x+j*dx[i]; xx.y=t.y+j*dy[i];
        if(xx.x<1||xx.x>n||xx.y<1||xx.y>n)break;
        xx.step=t.step+1;
        if(!a[xx.x][xx.y]){
          a[xx.x][xx.y]=2; // 已经走过过的打上标记 2
          if(xx.x==e.x&&xx.y==e.y){
            cout<<xx.step<<endl; return 0; // 搜到了
          }
          else q.emplace(xx);
        }
        else if(a[xx.x][xx.y]==1)break; // 这个是障碍物
      }
    }
  }
  cout<<"-1\n"; // 无解的情况
  return 0;
}