阿尔托莉雅丶 @ 2020-12-09 16:57:28
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
int offx[4] = {1, 0, -1, 0};
int offy[4] = {0, 1, 0, -1};
int sx, sy, ex, ey;
int n;
int map[1005][1005];
int dbfs(int sx, int sy, int ex, int ey) //sx表示startx,ex表示endx
{
queue<int> qs;
queue<int> qe;
int steps = 0, stepe = 0;
qs.push(sx); //首个点入队
qs.push(sy);
qs.push(steps);
map[sy][sx] = 2; //首个标记一下
qe.push(ex);
qe.push(ey);
qe.push(stepe);
map[ex][ey] = 3;
while(!qs.empty() && !qe.empty())
{
if(qs.size() <= qe.size()) //优先搜少的那边
{
sx = qs.front(); //出队
qs.pop();
sy = qs.front();
qs.pop();
steps = qs.front();
qs.pop();
steps++; //步数加一
for(int i = 0; i < 4; i++)
{
int dx = sx + offx[i];
int dy = sy + offy[i];
if(dy >= 0 && dx >= 0 && map[dy][dx] == 3) //如过重合了就返回step和
return stepe + steps;
if(dx >= 0 && dx < n && dy >= 0 && dy < n && map[dy][dx] == 0)
{
qs.push(dx);
qs.push(dy);
qs.push(steps);
map[dy][dx] = 2;
}
}
}
else //反向搜同理
{
ex = qe.front();
qe.pop();
ey = qe.front();
qe.pop();
stepe = qe.front();
qe.pop();
stepe++;
for(int i = 0; i < 4; i++)
{
int dx = ex + offx[i];
int dy = ey + offy[i];
if(dy >= 0 && dx >= 0 && map[dy][dx] == 2) //溢出
return stepe + steps;
if(dx >= 0 && dx < n && dy >= 0 && dy < n && map[dy][dx] == 0)
{
qe.push(dx);
qe.push(dy);
qe.push(stepe);
map[dy][dx] = 3;
}
}
}
}
return -1;
}
int main(void)
{
cin >> n;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
scanf("%1d", &map[i][j]);
}
cin >> sx >> sy >> ex >> ey;
cout<<dbfs(sx - 1, sy - 1, ex - 1, ey - 1); //从零开始下标
return 0;
}