求助
查看原帖
求助
1272259
cgxd楼主2024/6/7 08:46
#include<bits/stdc++.h>
#define reg register
#define y1 yone
using namespace std;
const int maxn = 2e3 + 3;
int n, m, x, y, sum, vis[maxn][maxn];
vector<vector<int>> v(1);
deque<complex<int>> dq;
const complex<int> dir[]{complex<int>(0, 1), complex<int>(1, 0), complex<int>(0, -1), complex<int>(-1, 0)};
int gcd(int x, int y){
	do
		swap(x, y);
	while(x %= y);
	return y;
}int main(){
	cin >> n >> m;
	for(reg int i = 1; i <= n; ++i){
		vector<int> vt(1);
		for(reg int j = 1; j <= m; ++j){
			int k;
			scanf("%d", &k);
			vt.push_back(k);
		}v.push_back(vt);
	}cin >> x >> y;
	if(v[x][y] == 1){
		cout << 0;
		return 0;
	}sum = v[x][y];
	vis[x][y] = 1;
	dq.push_back(complex<int>(x, y));
	while(dq.size()){
		complex<int> c(dq[0]);
		for(complex<int> c1: dir){
			complex<int> c2(c1 + c);
			int x1 = c2.real(), y1 = c2.imag();
			if(x1 <= 0 or y1 <= 0 or x1 > n or y1 > m or vis[x1][y1])
				continue;
			vis[x1][y1] = vis[x][y] + 1;
			dq.push_back(c2);
			sum = gcd(sum, v[x1][y1]);
			if(sum == 1){
				cout << vis[x][y];
				return 0;
			}
		}dq.pop_front();
	}cout << -1;
	return 0;
}
2024/6/7 08:46
加载中...