广搜 20分求调
查看原帖
广搜 20分求调
1331235
xumingyu2024楼主2024/12/29 11:27
#include <iostream>
#include <queue>
using namespace std;
const int N=1005;

int dx[]= {-1,0,0,1};
int dy[]= {0,-1,1,0};
int n,sum[N][N];
int x1,y1,x2,y2;
char a[N][N];


struct node {
	int x,y;
};
queue<node> q;

bool can_push(int x,int y) {
	if(a[x][y]=='1'||sum[x][y]>0||x>n||x<1||y>n||y<1)
		return 0;
	return 1;
}

int main() {
	cin>>n;

	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			cin>>a[i][j];
	cin>>x1>>y1>>x2>>y2;

	q.push((node) {x1,y1});
	sum[x1][y1]=1;
	while(!q.empty()) {
		
		node tmp=q.front();
		int xx=tmp.x,yy=tmp.y;
		
		q.pop();
		for(int i=1;i<4;i++){
			if(can_push(xx+dx[i],yy+dy[i])){
				
				q.push((node){xx+dx[i],yy+dy[i]});
				
				sum[xx+dx[i]][yy+dy[i]]=sum[xx][yy]+1;
			}
		}
	}
	cout<<sum[x2][y2]-1;
	return 0;
}
2024/12/29 11:27
加载中...