为什么这个过不了???
查看原帖
为什么这个过不了???
1168533
ytt122楼主2024/10/7 17:39
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
typedef pair<int,int>PII;
const int N =5e3 + 10, inf = 0x3f3f3f3f;
int n,m,q;
ll a[N][N];
struct node{
	int x;
	int y;
};
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
ll gcd(ll a,ll b)
{
	return b? gcd(b,a%b):a;
}
int vis[N][N];
void solve()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
			vis[i][j]=0;
		}
	}
	int x1,y1;
	cin>>x1>>y1;
	queue<node>q;
	q.push({x1,y1});
	ll ans=a[x1][y1];
	if(ans==1)
	{
		cout<<0<<endl;
		return;
	}
	vis[x1][y1]=1;
	ll cnt=0;
	while(!q.empty())
	{
		node k=q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
			int k1=k.x+dx[i],k2=k.y+dy[i];
			if (k1<1||k1>n||k2<1||k2>m||vis[k1][k2])
			{
				continue;
			}
			vis[k1][k2]=1;
			cnt++;
			q.push({k1,k2});
			ans=gcd(ans,a[k1][k2]);
			if(ans==1)
			{
				cout<<cnt<<endl;
				return;
			}
		}
	}
	cout<<-1<<endl;
}

	
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	
	
    int T=1;
    //cin>>T;
    while( T -- )
    {
        solve();
    }
    return 0;
}


2024/10/7 17:39
加载中...