双向广搜20pts求条
查看原帖
双向广搜20pts求条
933604
LYBT楼主2024/3/3 08:57
#include<bits/stdc++.h>
using namespace std;
inline int read(){
	char c=getchar();
	int sum=0,flag=1;
	while(!isdigit(c)){if(c=='-')flag=-1;c=getchar();}
	while(isdigit(c)){sum=(sum<<1)+(sum<<3)+(c^48),c=getchar();}
	return sum*flag;
}
inline void write(int x){
	if(x<0) x=(~x)+1,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10|48);
}
const int fx[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int n=read(),mp[1005][1005];
bool vis[1005][1005];
struct node{
	int x,y,cnt;
}s,t;
bool check(node a,node b){
	return abs(a.x-b.x)+abs(a.y-b.y)==1;
}//判断相遇
int bfs(node s,node t){
	queue<node>qf,qb;
	qf.push(s),qb.push(t);
	vis[s.x][s.y]=vis[t.x][t.y]=1;
	while(qf.size()&&qb.size()){
		node now;
		if(qf.size()<qb.size()){
			now=qf.front();qf.pop();
			for(int i=0;i<4;i++){
				int x=now.x+fx[i][0],y=now.y+fx[i][1];
				if(vis[x][y]||x>n||y>n||x<1||y<1||mp[x][y])
					continue;
				qf.push((node){x,y,now.cnt+1});
				vis[x][y]=1;
				if(check(qf.back(),qb.back())) 
					return qf.back().cnt+qb.back().cnt+1;
			}
		}
		else{
			now=qb.front();qb.pop();
			for(int i=0;i<4;i++){
				int x=now.x+fx[i][0],y=now.y+fx[i][1];
				if(vis[x][y]||x>n||y>n||x<1||y<1||mp[x][y])
					continue;
				qb.push((node){x,y,now.cnt+1});
				vis[x][y]=1;
				if(check(qf.back(),qb.back())) 
					return qf.back().cnt+qb.back().cnt+1;
			}		
		}
	}
	return -1;
}
int main(){
	for(int i=1;i<=n;i++){
		char c[1005];
		scanf("%s",c+1);
		for(int j=1;j<=n;j++){
			mp[i][j]=c[j]-'0';
		}
	}
	s.x=read(),s.y=read(),s.cnt=0;
	t.x=read(),t.y=read(),t.cnt=0;
	write(bfs(s,t));
	return 0;
}
2024/3/3 08:57
加载中...