7.公约移动 - 蓝桥云课 (lanqiao.cn)
问题描述
小蓝站在一个n行m列的方格图中间，方格图的每一个方格上都标有一个正整数。
如果两个相邻方格(上下左右四个方向相邻)内的数的最大公约数大于1，则可以从其中一个方格移动到另一个方格，当然也可以从另一个方格移回第一个方格。
假设小蓝开始时站在第r行第c列，请问小蓝可以移动到广格图内的多少个方格?
输入格式
输入的第一行包含两个整数n,m，用一个空格分隔，表示方格图的行数和列数。
接下来n行，每行包含m个正整数，相邻整数间用一个空格分隔，依次表示方格图中从第1行到第n行，每行从第1列到第m列中的数。
接下来一行包含两个整数r,c，用一个空格分隔，表示小蓝所在的行号和列号。
输出格式
输出一行包含一个整数，表示答案
import os
import sys
# 请在此输入您的代码
n,m=map(int,input().split())
num=[]
for i in range(n):
n1=list(map(int,input().split()))
num.append(n1)
r,c=map(int,input().split())
flag=[[-1]*m for _ in range(n)] #标记走过的路，-1表示没走过
direction=[(1,0),(-1,0),(0,1),(0,-1)]
def gcb(a,b): #求最大公约数
if a%b==0:
return b
else:
return gcb(b,a%b)
def dfs(x,y):
count=1 #开始位置
ans=[(x,y)] #保存可以走的坐标
flag[x][y]=1
while len(ans):
tx,ty=ans.pop()
for d in direction:
dx=tx+d[0]
dy=ty+d[1]
if 0<=dx<n and 0<=dy<m:
if flag[dx][dy]==-1 and gcb(num[tx][ty],num[dx][dy])>1:
count+=1
ans.append((dx,dy))
flag[dx][dy]=1
return count
print(dfs(r-1,c-1)) #r,c是行列，坐标索引从0开始，要减去1
