7243求助!!!!!!
  • 板块学术版
  • 楼主glorious_dream
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/8/20 09:15
  • 上次更新2023/11/4 09:57:45
查看原帖
7243求助!!!!!!
226367
glorious_dream楼主2021/8/20 09:15
#include<bits/stdc++.h>
using namespace std;
long long a[2100][2100];
const int dx[4] = {-1,0,1,0};
const int dy[4] = {0,-1,0,1};
int vis[2100][2100];
int n,m;
int x,y;
int gcd(int x,int y){
	if(y==0){
		return x;
	}
	return gcd(y,x%y);
}
queue<int>qx;
queue<int>qy;
queue<int>qs;
void bfs(){
	qx.push(x);
	qy.push(y);
	qs.push(0);
	vis[x][y] = 1;
	long long sum  = a[x][y];
	while(!qx.empty()){
		int x = qx.front();
		int y = qy.front();
		int s = qs.front();
		qx.pop();
		qy.pop();
		qs.pop();
		for(int i=0 ; i<4 ; i++){
			int xx = x+dx[i];
			int yy = y+dy[i];
			if(xx>=1 && yy>=1 && xx<=n && yy<=m && vis[xx][yy] == 0){
				vis[xx][yy] = 1;
				qx.push(xx);
				qy.push(yy);
				qs.push(s+1);
				sum = gcd(sum,a[xx][yy]);
				if(sum == 1){
					printf("%d",s+1);
					return ;
				}
			}
		}
	}
	printf("%d",-1);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1 ; i<=n ; i++){
		for(int j=1 ; j<=m ; j++){
			scanf("%lld",&a[i][j]);
		}
	}
	scanf("%d%d",&x,&y);
	if(a[x][y] == 1){
		printf("%d",0);
		return 0;
	}
	bfs();
	return 0;
}
2021/8/20 09:15
加载中...