题解 P7243 【最大公约数】

zjrdmd · 2021-01-03 11:45:23 · 题解

这题一眼看上去十分复杂，但是仔细想一想还是蛮简单的。

首先，我们模拟经过一天以后所有人的个性值，如果此时没有个性值为1的人，那么可以直接给出无解信息。

然后我们思考第二天那些人的个性值会变为1，显然是第一天个性值变为1的人周围的人，那么第三天呢？就是第二天个性值变为1的人周围的人，于是这就变成了一道搜索题，我们使用bfs模拟以上过程即可，由于每个人只会进入队列一次，所以此过程时间复杂度为O(nm)，预处理复杂度为(4\times nmloga)

code:

#include <iostream>
#include <cstdio>
#include <queue> 
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#define ri register int
#define int long long

inline int read() {
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}

const int N=2e3+5;
int n,m,xx,yy;
int last[N][N],now[N][N],vis[N][N];
int qx[5]={1,-1,0,0};
int qy[5]={0,0,-1,1};

struct node{
    int x,y,d;
};
std::queue<node>q;

int gcd(int x,int y){
    if(y==0)return x;
    else return gcd(y,x%y);
}

signed main(void){
    n=read(),m=read();
    for(ri i=1;i<=n;i++){
        for(ri j=1;j<=m;j++){
            last[i][j]=read(); 
        }
    } 
    xx=read(),yy=read();
    if(last[xx][yy]==1)printf("0"),exit(0);//特判 
    for(ri i=1;i<=n;i++){
        for(ri j=1;j<=m;j++){
            int ans=last[i][j];
            if(i!=1)ans=gcd(ans,last[i-1][j]);
            if(i!=n)ans=gcd(ans,last[i+1][j]);
            if(j!=1)ans=gcd(ans,last[i][j-1]);
            if(j!=m)ans=gcd(ans,last[i][j+1]);
            now[i][j]=ans;
        }
    }//计算第一天所有人的个性值 
    for(ri i=1;i<=n;i++){
        for(ri j=1;j<=m;j++){
            if(now[i][j]==1)q.push((node){i,j,1});
        }
    } //将个性值为1的人丢进队列 
    if(q.size()==0)printf("-1");//判断无解 
    while(q.size()){
        node p=q.front();q.pop();
        if(vis[p.x][p.y])continue;
        vis[p.x][p.y]=true;
        if(p.x==xx&&p.y==yy){
            printf("%d",p.d);exit(0);//找到答案 
        }
        for(ri i=0;i<4;i++){
            int px=p.x+qx[i],py=p.y+qy[i];
            if(!((px>=1&&px<=n&&py>=1&&py<=m)&&(!vis[px][py])))continue;
            q.push((node){px,py,p.d+1});//将他周围的4个人丢进队列，并标记他们最短第几天个性值为1 
        }
    }
    return 0;
}

最慢的点跑了1.93s（逃