同化的题解

时间限制: 1000ms

空间限制: 524288kB

题目描述

古人云：“近朱者赤近墨者黑”。这句话是很有道理的。这不鱼大大和一群苦命打工仔被安排进厂拧螺丝了。
进厂第一天，每个人拧螺丝的动力k都是不同且十分高涨的。但是当大家坐在一起后会聊天偷懒，导致第二天时，每个人的拧螺丝动力变为昨天自己和四周人拧螺丝动力的最大公约数。当拧螺丝动力掉到1时，鱼大大就会跑路。
厂子的老板会对鱼大大这群打工仔安排拧螺丝的位置，可以简单看成是一个N*M的矩阵。现有工厂座位安排表，鱼大大坐在第X行第Y列，问最少几天后鱼大大就会跑路

输入格式

第一行两个整数N，M，表示矩阵的行数和列数。
接下来 N 行，每行 M 个整数，第 i 行第 j 列的整数 表示为该位置的人第一天拧螺丝的动力。
接下来一行两个整数 X,Y，表示鱼大大的位置。

输出格式

一行一个整数表示鱼大大第几天会跑路
（若是动力永远不掉到1，则为不会跑路，输出-1）

样例

Input 1

2 2
2 2
1 2
2 1

Output 1

0

Input 2

2 2
2 2 
2 2
1 1

Output 2

-1

Input 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.

主要思路：

这个题目是一道bfs+gcd的题目。我们可以维护一个集合S，最初是只有这个元素，那么每一次变换的时候，S里的元素都会变成gcd(注：其中n表示S的长度)，注：因为是gcd，而上面的式子也可以转化成以此类推直到。每次变换S也会扩大，具体请看图，图是把S当成一个矩阵来看。

通过图可以发现，每次S扩大时，是把S中所有的边缘元素的相邻的上下左右的元素且没有在集合中出现过的元素给加入进来，而这就是一个bfs了。

最后在bfs中，如果当前这个元素<=1了，那么就跳出（因为这个元素会被枚举到，一定是在集合S中，而S中有一个<=1，那其他元素肯定也会<=1)

注：

题目中说了，如果永远不是1，输出-1

代码code：

#include<bits/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()
{
	queue<node> q;
	q.push({x,y,0});
	while(!q.empty())
	{
		auto tmp = q.front();
		q.pop();
		int x1=tmp.x,y1=tmp.y,step = tmp.step;
		if(a[x1][y1] == 1)//如果这个元素为一 
		{
			ret=step;
			return ;
		}
		for(int i=0;i<4;i++)//上下左右四个方向 
		{
			int tx=x1+dx[i],ty=y1+dy[i];
			if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&!vis[tx][ty])
			{
				vis[tx][ty] = 1;//标记 
				a[tx][ty] = __gcd(a[x1][y1],a[tx][ty]);//取个gcd 
				q.push({tx,ty,step+1});//加入集合 
			}
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	 } 
	cin>>x>>y;
	bfs();
	cout<<ret;
	return 0;
}