绍兴网站制作网站,做牙的网站叫什么,物联网专业就业方向,建设工程竣工规划局网站时间限制: 1000ms
空间限制: 524288kB
题目描述
古人云#xff1a;“近朱者赤近墨者黑”。这句话是很有道理的。这不鱼大大和一群苦命打工仔被安排进厂拧螺丝了。 进厂第一天#xff0c;每个人拧螺丝的动力k都是不同且十分高涨的。但是当大家坐在一起后会聊天偷懒#xf…时间限制: 1000ms
空间限制: 524288kB
题目描述
古人云“近朱者赤近墨者黑”。这句话是很有道理的。这不鱼大大和一群苦命打工仔被安排进厂拧螺丝了。 进厂第一天每个人拧螺丝的动力k都是不同且十分高涨的。但是当大家坐在一起后会聊天偷懒导致第二天时每个人的拧螺丝动力变为昨天自己和四周人拧螺丝动力的最大公约数。当拧螺丝动力掉到1时鱼大大就会跑路。 厂子的老板会对鱼大大这群打工仔安排拧螺丝的位置可以简单看成是一个N*M的矩阵。现有工厂座位安排表鱼大大坐在第X行第Y列问最少几天后鱼大大就会跑路
输入格式
第一行两个整数NM表示矩阵的行数和列数。 接下来 N 行每行 M 个整数第 i 行第 j 列的整数 表示为该位置的人第一天拧螺丝的动力。 接下来一行两个整数 X,Y表示鱼大大的位置。
输出格式
一行一个整数表示鱼大大第几天会跑路 若是动力永远不掉到1则为不会跑路输出-1
样例
Input 1 2 2
2 2
1 2
2 1 Output 1 0Input 2 2 2
2 2
2 2
1 1 Output 2 -1Input 3 3 3
3 2 3
2 3 2
3 2 3
2 2 Output 3 1 数据范围
2 ≤ N,M ≤ 1000; 1 ≤ ≤ 100000; 保证X,Y合法即鱼大大位置肯定在矩阵范围中
题目大意
有一个N*M的矩阵对其进行变换将矩阵中的每一个元素变为其上下左右及自身不存在则忽略的最大公约数。问多少次变换后会变成1.
主要思路
这个题目是一道bfsgcd的题目。我们可以维护一个集合S最初是只有这个元素那么每一次变换的时候S里的元素都会变成gcd(注其中n表示S的长度)注因为是gcd而上面的式子也可以转化成以此类推直到。每次变换S也会扩大具体请看图图是把S当成一个矩阵来看。 图示1 通过图可以发现每次S扩大时是把S中所有的边缘元素的相邻的上下左右的元素且没有在集合中出现过的元素给加入进来而这就是一个bfs了。
最后在bfs中如果当前这个元素1了那么就跳出因为这个元素会被枚举到一定是在集合S中而S中有一个1那其他元素肯定也会1)
注
题目中说了如果永远不是1输出-1
代码code
#includebits/stdc.h
using namespace std;
int a[1010][1010];
int n,m;
int vis[1010][1010];
int ret-1;//没有输出-1
int x,y;
int dx[] {0,-1,0,1};
int dy[] {1,0,-1,0};
struct node{int x,y,step;
};
void bfs()
{queuenode q;q.push({x,y,0});while(!q.empty()){auto tmp q.front();q.pop();int x1tmp.x,y1tmp.y,step tmp.step;if(a[x1][y1] 1)//如果这个元素为一 {retstep;return ;}for(int i0;i4;i)//上下左右四个方向 {int txx1dx[i],tyy1dy[i];if(tx1txnty1tym!vis[tx][ty]){vis[tx][ty] 1;//标记 a[tx][ty] __gcd(a[x1][y1],a[tx][ty]);//取个gcd q.push({tx,ty,step1});//加入集合 }}}
}
int main()
{cinnm;for(int i1;in;i){for(int j1;jm;j){cina[i][j];}} cinxy;bfs();coutret;return 0;
}
