We have an $N \times 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. We have put a white bishop on the square $(A_x, A_y)$. A white bishop on the square $(i, j)$ can go to the following positions in one move. For each positive integer $d$, it can go to $(i+d,j+d)$ if all of the conditions are satisfied. For each positive integer $d$, it can go to $(i+d,j-d)$ if all of the conditions are satisfied. For each positive integer $d$, it can go to $(i-d,j+d)$ if all of the conditions are satisfied. For each positive integer $d$, it can go to $(i-d,j-d)$ if all of the conditions are satisfied.Problem Statement
The board is described by $N$ strings $S_i$.
The $j$-th character of the string $S_i$, $S_{i,j}$, means the following.
., the square $(i, j)$ is empty.#, the square $(i, j)$ is occupied by a white pawn, which cannot be moved or removed.
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
Constraints
. and #...
Input
Input is given from Standard Input in the following format:
$N$ $A_x$ $A_y$ $B_x$ $B_y$ $S_1$ $S_2$ $\vdots$ $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) \rightarrow (2,2) \rightarrow (4,4) \rightarrow (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 .................. .####............. .#..#..####....... .####..#..#..####. .#..#..###...#.... .#..#..#..#..#.... .......####..#.... .............####. .................. .................. .####............. ....#..#..#....... .####..#..#..####. .#.....####..#.... .####.....#..####. ..........#..#..#. .............####. ..................
其实我们可以有另外一种理解方式：代价相当于在移动过程中转向的次数。我们可以记录上一步走的是那个方向，然后这一步的代价就是是否和上一步不等。
发现代价只有 0 或 1，01BFS 即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1505,M=N*N*4,dx[]={1,-1,1,-1},dy[]={1,-1,-1,1};
int dp[N][N][4],n,sx,sy,ex,ey,l=1,r;
char s[N][N];
int mo(int x)
{
return (x%M+M)%M;
}
int ok(int x,int y)
{
return x>0&&y>0&&x<=n&&y<=n&&s[x][y]=='.';
}
struct node{
int x,y,t;
}q[M];
int main()
{
scanf("%d%d%d%d%d",&n,&sx,&sy,&ex,&ey);
for(int i=1;i<=n;i++)
scanf("%s",s[i]+1);
memset(dp,0x7f,sizeof(dp));
dp[sx][sy][0]=dp[sx][sy][2]=dp[sx][sy][3]=dp[sx][sy][1]=1;
for(int i=0;i<4;i++)
q[++r]=(node){sx,sy,i};
while(l<=r)
{
// printf("%d %d\n",l,r);
int x=q[mo(l)].x,y=q[mo(l)].y,t=q[mo(l)].t;
++l;
for(int i=0;i<4;i++)
{
int tx=x+dx[i],ty=y+dy[i];
if(ok(tx,ty))
{
if(dp[x][y][t]+(i!=t)>=dp[tx][ty][i])
continue;
dp[tx][ty][i]=dp[x][y][t]+(i!=t);
if(i==t)
{
--l;
q[mo(l)]=(node){tx,ty,i};
}
else
{
++r;
q[mo(r)]=(node){tx,ty,i};
}
}
}
}
// for(int i=1;i<=n;i++)
// {
// for(int j=1;j<=n;j++)
// printf("%d ",min(min(dp[i][j][0],dp[i][j][1]),min(dp[i][j][2],dp[i][j][3])));
// putchar('\n');
// }
int ans=min(min(dp[ex][ey][0],dp[ex][ey][1]),min(dp[ex][ey][2],dp[ex][ey][3]));
printf("%d",ans>2e9? -1:ans);
}