10分9RE求调
查看原帖
10分9RE求调
1764362
ygwt楼主2025/8/1 12:36
#include <iostream>
using namespace std;
const int N=1000001;
int n;
char G[1001][1001];
int vis[1001][1001];
int x1,y1,x2,y2;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int step=N;
int sum;
int MIN(int a,int b)
{
	return a<b ? a : b;
}
void bfs(int x,int y)
{
	if(x==x2&&y==y2){
		step=MIN(step,sum);
		return;
	}
	for(int i=0;i<4;i++){
		int xx=x+dx[i],yy=y+dy[i];
		if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&G[xx][yy]=='0'&&vis[xx][yy]==0){
			sum++;
			vis[x][y]=1;
			bfs(xx,yy);
			vis[x][y]=0;
			sum--;
		}
	}
	return;
}
void show()
{
	cout<<step;
}
//主函数
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>G[i][j];
		}
	}
	cin>>x1>>y1>>x2>>y2;
	vis[x1][y1]=1;
	bfs(x1,y1);
	show();
	//结束
	return 0;
}
2025/8/1 12:36
加载中...