Re: [問題] 判斷相同符號的演算法

[pziyout (pziyout)]

※ 引述《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://www.ptt.cc/bbs/Python/M.1555558933.A.052.html
推 stfang925: 推
推 wavek: 推
推 chaotic0307: 推
推 TitanEric: 1. valid那裡可以直接回傳 不用再if else
→ TitanEric: 2. 四個方位那裡寫成一個array 然後for loop跑過 會比
→ TitanEric: 較好
推 germun: 小矩陣像這樣用遞迴就夠了, 大矩陣用遞迴可能會爆
推 lemon651: valid寫在最上面不就行了嗎
→ thefattiger: 為何耀挑這種小瑕疵...又不是production code
推 HenryLiKing: 同意樓上  原PO厲害!!