Algorithm_ZRF @ 2024-02-01 14:55:07
#include <bits/stdc++.h>
#define maxn 1005
using namespace std;
int dx[] = {1,-1,0,0},
dy[] = {0,0,1,-1};
struct co {
int x,y;
};
struct ss {
int x,y,dis;
};
int n;
co Start,End;
char Mp[maxn][maxn];
int mp[maxn][maxn];
bool check(int a,int b) {
return a < 0 || b < 0 || a > n || b > n;
}
inline void Read() {
scanf("%d",&n);
for(int i = 1; i <= n; ++i) {
for(int j = 1;j <= n;++j){
scanf(" %c",&Mp[i][j]);
mp[i][j] = Mp[i][j] - '0';
}
}
scanf("%d%d%d%d",&Start.x,&Start.y,&End.x,&End.y);
}
inline int double_BFS(int sx,int sy,int ex,int ey,int sdis,int edis) {
queue<ss> sq,eq;
ss s1, s2;
s1.x = sx,
s1.y = sy,
s1.dis = sdis,
s2.x = ex,
s2.y = ey,
s2.dis = edis;
sq.push(s1),eq.push(s2);
while(1) {
ss snow = sq.front(),enow = eq.front();
sq.pop(),eq.pop();
if(snow.x == enow.x && snow.y == enow.y) {
return snow.dis + enow.dis;
}
for(int i = 0; i < 4; ++i) {
int stx,sty,stdis;
stx = snow.x + dx[i],
sty = snow.y + dy[i],
stdis = snow.dis + 1;
if(check(stx,sty)) continue;
if(mp[stx][sty] == 1)continue;
mp[stx][sty] == 1;
sq.push({stx,sty,stdis});
}
for(int i = 0; i < 4; ++i) {
int etx,ety,etdis;
etx = enow.x + dx[i],
ety = enow.y + dy[i],
etdis = enow.dis + 1;
if(check(etx,ety)) continue;
if(mp[etx][ety] == 1)continue;
mp[etx][ety] == 1;
eq.push({etx,ety,etdis});
}
}
}
inline void solve() {
Read();
printf("%d",double_BFS(Start.x,Start.y,End.x,End.y,0,0));
}
int main() {
solve();
exit(0);
}by The_Chariot @ 2024-02-01 17:40:24
不写vis数组的危害，本人亲测（（（
@Algorithm_ZRF
by The_Chariot @ 2024-02-01 17:47:06
@Algorithm_ZRF 还有我没看懂你这个BFS，其实这就一BFS板子题，不用那么复杂，读入也正常读入就可以，下附核心代码：
queue<node>q;
void bfs()
{
node now,next;
vis[sx][sy]=1;
now.x=sx,now.y=sy,now.step=0;
q.push(now);
while(!q.empty())
{
now=q.front();
q.pop();
for(int i=0;i<4;++i)
{
next.x=now.x+dirx[i],next.y=now.y+diry[i],next.step=now.step+1;
if(next.x==ex&&next.y==ey)
{
ans=next.step;
return ;
}
if(next.x>0&&next.y>0&&next.x<=n&&next.y<=n&&mapp[next.x][next.y]=='0'&&vis[next.x][next.y]==0)
{
vis[next.x][next.y]=1;
q.push(next);
}
}
}
}by Algorithm_ZRF @ 2024-02-01 18:00:46
@The_Chariot 我用双向BFS做的
by Algorithm_ZRF @ 2024-02-01 18:04:18
@The_Chariot 而且mp就是我的vis啊