求调
查看原帖
求调
785681
shenzixin楼主2024/3/2 22:44
#include<bits/stdc++.h>
using namespace std;

struct Node {
	long long x, y,z;
};

long long m, n, x, y;
long long a[2009][2009];
int fi[10] = { 0, 0, -1, -1, -1, 1, 1, 1 };
int se[10] = { 1, -1, -1, 0, 1, -1, 0, 1 };
long long mi;
queue<Node> qu;

long long gcd(long long a, long long b) {// 大小
	long long m = max(a, b);
	b = a + b - m;
	a = m;
	if (a % b == 0) { 
		return b;
	}
	else {
		return gcd(b, a % b);
	}
}

int main() {
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
		}
	}
	cin >> x >> y;

	x--;
	y--;

	Node one;
	one.x = x;
	one.y = y;
	one.z = a[x][y];
	qu.push(one);
	mi = a[x][y];
	a[x][y] = -1;

	while (!qu.empty()) {
		long long sx, sy;
		mi = gcd(mi, qu.front().z);
		if (mi == 1) {
			cout << max(abs(qu.front().x - x) , abs(qu.front().y - y));
			return 0;
		}

		for (int i = 0; i < 8; i++) {
			sx = qu.front().x + fi[i];
			sy = qu.front().y + se[i];
			if (sx >= 0 and sy >= 0 and sx < m and sy < n and a[sx][sy]!=-1) {
				one.x = sx;
				one.y = sy;
				one.z = a[sx][sy];
				qu.push(one);
				a[sx][sy] = -1;
			}
		}

		qu.pop();
	}
	cout << -1;
}
2024/3/2 22:44
加载中...