#include<bits/stdc++.h>
using namespace std;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
long long n,m,a[2002][2002],vis[2002][2002],s,x,y,res;
struct node
{
int x,y,ans;
};
queue<node>q;
void bfs()
{
while(!q.empty())
{
node now=q.front();
q.pop();
res=__gcd(res,a[now.x][now.y]);
if(res==1)
{
cout<<now.ans;
return;
}
for(int i=0;i<4;++i)
{
int nx=now.x+dx[i];
int ny=now.y+dy[i];
if(nx>=1&&ny>=1&&nx<=n&&ny<=m&&!vis[nx][ny])
{
vis[nx][ny]=1;
q.push({nx,ny,now.ans+1});
}
}
}
}
int main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
scanf("%lld",&a[i][j]);
if(a[i][j]==a[1][1]) s++;
}
scanf("%lld%lld",&x,&y);
if(s==n*m)
{
printf("-1");
return 0;
}
s=0;
vis[x][y]=1;
res=a[x][y];
q.push({x,y,0});
if(res==1)
{
cout<<0;
return 0;
}
bfs();
return 0;
}
4 个赞
你的思路是对的
广搜：只要一个点变成1，输出step+1(这个点成为1除外)
然后提前判断掉-1的情况
3 个赞
一下是本蒟蒻的代码（大佬代码改不出来）：
#include<bits/stdc++.h>
using namespace std;
template<class T>inline void read(T &x){x = 0;T f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-'){f=-1;}ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}x*=f;}
long long a[2003][2003];
long long gcd(long long x, long long y){while(y^=x^=y^=x%=y);return x;}
int dx[5]={0, 1, 0, -1};
int dy[5]={1, 0, -1, 0};
struct node{
int x, y,step;
}q[10000001];
bool vis[2001][2001];
int main(){
int n, m;
read(n);
read(m);
for(register int i=1; i<=n; ++i){
for(register int j=1; j<=m; ++j){
read(a[i][j]);
}
}
int x, y;
read(x);
read(y);
int head=1,tail=0;
q[++tail]=(node){x,y,0};
long long s=a[x][y];
vis[x][y]=1;
while(head<=tail){
node h=q[head];
head++;
if(s==1){
cout<<h.step;
return 0;
}
for(int i=0;i<4;i++){
int xx=h.x+dx[i];
int yy=h.y+dy[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]){
vis[xx][yy]=1;
s=gcd(s,a[xx][yy]);
if(s==1){
cout<<h.step+1;
return 0;
}else{
node w=(node){xx,yy,h.step+1};
q[++tail]=w;
}
}
}
}
cout<<-1;
}
3 个赞