ABC246 E:Bishop 2题解

· · 个人记录

\text{题目}

原题连接：https://atcoder.jp/contests/abc246/tasks/abc246_e

E - Bishop 2

Time Limit: 6 sec / Memory Limit: 2048 MB

Score : 500 points

Problem Statement

We have an N×N chessboard. Let (i,j) denote the square at the i-th row from the top and j-th column from the left of this board. The board is described by N strings S_i. The j-th character of the string S_i , S_{i,j} , means the following.

Find the minimum number of moves needed to move this bishop from (A_x,A_y) to (B_x ,B_y) according to the rules of chess (see Notes). If it cannot be moved to (B_x ,B_y), report -1 instead.

Notes

A white bishop on the square (i,j) can go to the following positions in one move.

Constraints

Input

Input is given from Standard Input in the following format:

N A_x\space A_y B_x\space B_y S_1 S_2 ⋮ S_N

Output

Print the answer.

Sample Input 1

5
1 3
3 5
....#
...#.
.....
.#...
#....

Sample Output 1

3

We can move the bishop from (1,3) to (3,5) in three moves as follows, but not in two or fewer moves.

(1,3)→(2,2)→(4,4)→(3,5)

Sample Input 2

4
3 2
4 2
....
....
....
....

Sample Output 2

-1

There is no way to move the bishop from (3,2) to (4,2).

Sample Input 3

18
18 1
1 18
..................
.####.............
.#..#..####.......
.####..#..#..####.
.#..#..###...#....
.#..#..#..#..#....
.......####..#....
.............####.
..................
..................
.####.............
....#..#..#.......
.####..#..#..####.
.#.....####..#....
.####.....#..####.
..........#..#..#.
.............####.
..................

Sample Output 3

9

\text{题意简述}

英语好的大佬们应该不用看

给定一个国际象棋中的象及若干个不可移动的障碍物，求象从给定点 (A_x ,A_y) 到 (B_x ,B_y) 的最少步数。

\text{题目分析}

为什么这道题没有在题库里？

比较厉害的OIer应该很快就发现这是一道BFS题，可以使用隐式图做法，背过模板精通编程的人可以用BFS走迷宫的模板，当然，CSP或NOIP当天是不会让大家带模板U盘去的（废话）。下面我将给出3种做法。

\text{解法一：BFS}

这是我第一次采用的做法，简单粗暴，直接上代码。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1500+10;
int n,dis[MAXN][MAXN];//n<=1500
bool vis[MAXN][MAXN],blocked[MAXN][MAXN];//两种情况：走不通和已访问分开处理。
char cur;
struct pos{
  int x,y;
}s,e,dpos[]={{1,1},{1,-1},{-1,1},{-1,-1}};
bool operator==(pos a,pos b){
  return a.x==b.x&&a.y==b.y;
}
queue<pos> q;
queue<pos> get_pos(pos p){//获得下一步能去的节点
  queue<pos> retVal;
  pos cur=p;
  while(!blocked[++cur.x][++cur.y]) if(!vis[cur.x][cur.y]) retVal.push(cur);
  cur=p;
  while(!blocked[--cur.x][++cur.y]) if(!vis[cur.x][cur.y]) retVal.push(cur);
  cur=p;
  while(!blocked[++cur.x][--cur.y]) if(!vis[cur.x][cur.y]) retVal.push(cur);
  cur=p;
  while(!blocked[--cur.x][--cur.y]) if(!vis[cur.x][cur.y]) retVal.push(cur);
  return retVal;
}
int main(){
  cin>>n;
  cin>>s.x>>s.y;
  cin>>e.x>>e.y;
  for(int i=0;i<=n+1;i++) blocked[0][i]=blocked[i][0]=blocked[n+1][i]=blocked[i][n+1]=true;//边界
  for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){
    cin>>cur;
    dis[i][j]=-1;
    if(cur=='#') blocked[i][j]=true;
  }
  vis[s.x][s.y]=true;
  dis[s.x][s.y]=0;
  q.push(s);
  while(!q.empty()){
    pos cur=q.front();
    q.pop();
    queue<pos> nxt=get_pos(cur);
 //   cout<<cur.x<<" "<<cur.y<<"->"<<endl;
    while(!nxt.empty()){
     //     cout<<nxt.front().x<<" "front().y<<endl;
      int x1=nxt.front().x,y1=nxt.front().y;
      if(dis[x1][y1]!=-1) return 2147483647;//assert
      q.push(nxt.front());//新节点入队
      vis[x1][y1]=true;
      dis[x1][y1]=dis[cur.x][cur.y]+1;//记录距离
      if(nxt.front()==e) break;//如果是目标节点，程序结束
      nxt.pop();
    }
  }
  cout<<dis[e.x][e.y];
  return 0;
}

注意访问和阻挡要分开考虑。

\text{方法二：BFS}

你没看错，还是BFS。

每一次只走一步，判断对答案有没有贡献。如果这次的方向和上一次相同就有贡献，否则没有。

\text{方法三：deque优化}

在方法二的基础上，如果对答案没有贡献的放在队头，优先考虑。

\text{我的DEBUG日志}


220418 代码完成
220421 找到BUG并调试
|- BUG：访问过和被阻挡放到一起考虑，结果错误。
\- 当天AC