作者pziyout (pziyout)
看板Python
标题Re: [问题] 判断相同符号的演算法
时间Thu Apr 18 11:42:11 2019
※ 引述《leo52127 (龙...)》之铭言：
: 假设 5*5 25格 每格都有一个1~8数字(随机)
: 想请问如果我想判断这25格中
: 有没有相同的数字连在一起(6个以上连在一起)
: 然後输出结果
: 举例：
: 1 1 2 3 2
: 2 1 5 6 7
: 4 1 6 2 8
: 1 1 1 7 8
: 1 3 4 5 5
: 输出： 1 8连
: 2 3 3 5 8
: 2 4 3 3 3
: 2 2 1 3 7
: 2 2 2 4 4
: 2 1 7 7 5
: 输出： 2 8连 3 6连
: 想了好几天了，都想不出来...
: 拜托版上的大大帮帮小弟
简单的递回问题，用 python 写程式都满简短的，
以下为在 nxn 的方阵先用乱数填入 [a,b] 范围数字，然後使用
递回函式检查相连同数字位置，将位置存起来，位置的个数就是相连的数量。
import random
# (i,j) 是否在 [0,n-1]x[0,n-1] 之间
def valid( n , i , j ) :
return True if ( 0 <= i < n and 0 <= j < n ) else False
# 检查 (i,j) 是否为数字 num，若是记录位置并继续其余为走过位置寻找相同数字
def forward( num , i , j , visited ) :
global lands
if lands[i][j] == num :
visited.add( (i,j) )
if valid( n , i+1 , j ) :
if (i+1,j) not in visited : forward(num,i+1,j,visited)
if valid( n , i-1 , j ) :
if (i-1,j) not in visited : forward(num,i-1,j,visited)
if valid( n , i , j+1 ) :
if (i,j+1) not in visited : forward(num,i,j+1,visited)
if valid( n , i , j-1 ) :
if (i,j-1) not in visited : forward(num,i,j-1,visited)
a , b = 1 , 5
n = 10
lands = [ [ random.randint(a,b) for i in range(n) ] for j in range(n) ]
# 检查所有数字
for num in range(a,b+1) :
print( num , end=":\n" )
total , loc_visiteds = [] , []
for i in range(n) :
for j in range(n) :
# 跳过已走过的相连位置
if (i,j) in loc_visiteds : continue
visited = set()
forward(num,i,j,visited)
if len(visited) > 1 :
loc_visiteds += [ p for p in visited ]
print( " {} 连：".format( len(visited) ) +
" , ".join( [ "[{},{}]".format(p[0],p[1])
for p in sorted(visited) ] ) )
total += [ len(visited) ]
print( " 最大相连个数：" , max(total) , "连" , end="\n\n" )
for r in lands :
print( " ".join( [ str(v) for v in r ] ) )
----------------------------------
数字分布在最下方:
1:
2 连：[0,4] , [0,5]
2 连：[2,5] , [2,6]
2 连：[5,8] , [5,9]
2 连：[7,1] , [7,2]
3 连：[7,7] , [8,6] , [8,7]
最大相连个数： 3 连
2:
2 连：[3,8] , [3,9]
4 连：[4,6] , [5,6] , [5,7] , [6,6]
2 连：[8,3] , [9,3]
最大相连个数： 4 连
3:
2 连：[1,3] , [2,3]
4 连：[3,0] , [4,0] , [4,1] , [5,0]
4 连：[7,3] , [7,4] , [7,5] , [8,5]
2 连：[8,2] , [9,2]
2 连：[8,8] , [8,9]
最大相连个数： 4 连
4:
2 连：[0,6] , [0,7]
4 连：[1,4] , [2,4] , [3,4] , [4,4]
6 连：[3,2] , [4,2] , [5,1] , [5,2] , [6,1] , [6,2]
最大相连个数： 6 连
5:
2 连：[2,7] , [3,7]
3 连：[3,3] , [4,3] , [5,3]
2 连：[3,5] , [4,5]
2 连：[4,8] , [4,9]
2 连：[8,1] , [9,1]
2 连：[9,6] , [9,7]
最大相连个数： 3 连
1 3 4 5 1 1 4 4 3 2
2 5 1 3 4 2 5 3 4 5
5 3 2 3 4 1 1 5 3 4
3 1 4 5 4 5 4 5 2 2
3 3 4 5 4 5 2 4 5 5
3 4 4 5 1 3 2 2 1 1
2 4 4 1 2 5 2 5 4 3
4 1 1 3 3 3 5 1 5 4
1 5 3 2 4 3 1 1 3 3
4 5 3 2 5 2 5 5 4 2
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.115.25.29
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Python/M.1555558933.A.052.html
1F：推 stfang925: 推 04/18 11:49
2F：推 wavek: 推 04/18 12:32
3F：推 chaotic0307: 推 04/18 17:32
4F：推 TitanEric: 1. valid那里可以直接回传 不用再if else 04/18 21:00
5F：→ TitanEric: 2. 四个方位那里写成一个array 然後for loop跑过 会比 04/18 21:00
6F：→ TitanEric: 较好 04/18 21:00
7F：推 germun: 小矩阵像这样用递回就够了, 大矩阵用递回可能会爆 04/19 02:45
8F：推 lemon651: valid写在最上面不就行了吗 04/19 09:34
9F：→ thefattiger: 为何耀挑这种小瑕疵...又不是production code 04/19 22:01
10F：推 HenryLiKing: 同意楼上 原PO厉害!! 04/20 13:31