Pythonで乱数を使って出来た、２次元配列内の中から特定の形を持った図形の頂点（接点）を赤色に塗って出力したい。

Question

前提・実現したいこと

現在、pythonを使ってアルゴリズムやデータ構造などを勉強中なのですが、
問題につまずいてしまいヘルプをお願いしたいです。

乱数を発生させる為に2つの整数を入力します。この整数の最初の数は乱数を発生させるための数字で、
後ろの数は１の発生率になります。
数が大きくなればなるほど、１０*１０の枠組みの中の１の数が増えます。
その中から、縦と横の、（斜めは含めません）連続する１のみで出来た歪な図形の杭（spike)の部分を赤色に染めて出力するという問題なのですが、logicが分からずに困惑しています。

　下の写真はそれに応じた出力結果になります。ちなみに、枠組みの中に１でできた図形が複数ある場合はその中から、最大の面積をもつ図形の杭を出力させます（黄色に塗ってあるのはその図形を見易くするためで出力とは関係ありません）。

該当のソースコード

from random import seed, randrange
import sys


dim = 10


def display_grid():
    for row in grid:
        print('   ', *row)
 
def colour_shapes():
    pass

def max_number_of_spikes(nb_of_shapes):
    pass

try: 
    for_seed, density = (int(x) for x in input('Enter two integers, the second '
                                               'one being strictly positive: '
                                              ).split()
                    )
    if density <= 0:
        raise ValueError
except ValueError:
    print('Incorrect input, giving up.')
    sys.exit()

seed(for_seed)
grid = [[int(randrange(density) != 0) for _ in range(dim)]
            for _ in range(dim)
       ]
print('Here is the grid that has been generated:')
display_grid()
nb_of_shapes = colour_shapes()
print('The maximum number of spikes of some shape is:',
      max_number_of_spikes(nb_of_shapes)
     )

試したこと

from random import seed, randrange
import sys

dim = 10


def display_grid():
    for row in grid:
        print('   ', *row) 

def colour_shapes():
    pass

maxArea = 0

def display_grid():
    for row in grid:
        print('   ', *row) 

def max_number_of_spikes(nb_of_shapes):
    global maxArea
    for i in range(dim*dim):
      # fixed point 
      x = i % dim
      y = i // dim
      # from fixed point to right side until the wall 
      for j in range(2,dim+1-x):
        #print(f'x={x}, y={y}, j={j}')
        area = is_safe(x,y,j)
        if area != 0:
          # to search under
          for k in range(1,dim-y):
            # y axis += 1 
            area2 = is_safe(x,y+k,j)
            if area2 == 0:
              if k==1:
                area = 0
              break
            else:
              area += area2
          #print(x,y,j,area) #x,y, length, area
          maxArea = max(maxArea, area)
            # to search for left under 
    return maxArea

def is_safe(x,y,length):
  result = 0
  # if x is not over the left side  
  if x < 0:
    return 0
  # if x is not over the dimention (10*10 grid)
  if x+length > dim:
    return 0
  for xi in range(length):
    result += grid[y][x+xi]
  if result == length:
    return result
  else:
    return 0


try: 
    for_seed, density = (int(x) for x in input('Enter two integers, the second '
                                               'one being strictly positive: '
                                              ).split()
                    )
    if density <= 0:
        raise ValueError
except ValueError:
    print('Incorrect input, giving up.')
    sys.exit()

seed(for_seed)
grid = [[int(randrange(density) != 0) for _ in range(dim)]
            for _ in range(dim)
       ]
print('Here is the grid that has been generated:')
display_grid()
nb_of_shapes = colour_shapes()
print('The maximum number of spikes of some shape is:',
      max_number_of_spikes(nb_of_shapes)
     )

自分のコードで２次元配列の枠組みの行と列を1つずつみて行って、その中から出来た最大面積の図形を返す関数とis_safeで枠組みの中からはみ出していたり、１ではない時には０を返すという関数を作ったのですが、
出力が違いダメでした。color_shapes内の関数はまだ杭が見つけられてないのでpassしています。最初からコードを書き直す形でも自分的には問題ないので、問題が解ける方が居ましたら、
お助けいただけば幸いです。よろしくお願い致します。

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Comments

[meg_]

学校の課題でしょうか？

[8524ba23]

問題の出典があれば記載ください。（↓でしょうか）
https://www.coursehero.com/file/22706794/Week-6-quiz-5py/

[Ana_00]

はい、その通りです。なるべく自分で解きたいのですが、何日間かけても解けず、もう時間に余裕がなく、
困惑しています。自力で解かなくては意味がないと思うので、コードを欲しいのではないです。それにつながるヒントやこう考えるといい、などの思考だけでもと思い投稿させて頂きました。

[Ana_00]

can110 さん。はい残念ながらそちらに記載されています問題と全く同じ問題です。私と同じ科目を取っている不特定多数の誰かが投稿したのだと思われます。

[Ana_00]

can110さん、すみません、その問題はぱっと見ですと非常に似ていますが少し問題文などが違うと思われます。

[meg_]

> 最初からコードを書き直す形でも自分的には問題ないので、問題が解ける方が居ましたら、お助けいただけば幸いです。
上記記述より「丸投げ？」と思ってしまいましたが、
> 自力で解かなくては意味がないと思うので、コードを欲しいのではないです。それにつながるヒントやこう考えるといい、などの思考だけでもと思い
だったのですね。

質問文にそのあたりを明記されると考え方の回答が付きやすくなるかと思います。

[Ana_00]

meg_ さん、返信の方をありがとうございます。確かに上の文章だと丸投げ感が強いので今後は気をつけます。ご指摘ありがとうございました。

[fana]

適当な方法で４隣接でラベリングして，（最大の島に関して）連結数１の場所をピックアップするだけの話に見えますね．
（ところで，同じ面積の島が複数あったらどうする？）

Answer 1

以下のような再帰コードで1を「なぞる」ことができますので参考にしてください。
dim=30くらいまでなら動作します。

import pprint

dim = 10

# 探索
def search(grid, x, y):
    # 範囲外
    if not (x >= 0 and x < dim and y >= 0 and y < dim):
        return
    # 探索対象外
    if grid[y][x] != 1:
        return

    grid[y][x] = 2 # 探索済
    print(f'{x},{y}')

    # 上下左右に探索
    search(grid, x, y-1)
    search(grid, x, y+1)
    search(grid, x-1, y)
    search(grid, x+1, y)

# ケース：単純例
grid = [[0 for _ in range(dim)] for _ in range(dim)]
grid[0][0] = grid[0][1] = grid[0][2] = grid[1][1] = 1
pprint.pprint(grid)
search(grid, 0, 0) # (0,0)から探索
pprint.pprint(grid)

# ケース：最悪例
grid = [[1 for _ in range(dim)] for _ in range(dim)]
pprint.pprint(grid)
search(grid, 0, 0) # (0,0)から探索
pprint.pprint(grid)

Comments

[Ana_00]

can110さん、ありがとうございます。参考にさせて頂きます。

Answer 2

たとえば、spikeは隣接する縦横4つの要素のうち3つが非1(0, あるいは外周)というのを利用してはいかがでしょう。
すいません、一番面積が大きいものというのを読み落としていました。
迷路探索のようにして、出発杭から各杭への経路を合計するとかでしょうか。（いや、なんか重そうな処理ですね。もっとスマートな手法を他の人が書いてくれそう）

追記1

たとえば適当な1から出発して、隣接する1を全て2に置き換える。それを終えたら他の1から出発して3に置き換える...とかすると、どの数字が一番含まれてるかをカウント（numpyとかにそういう機能ありますね）すれば、最大の島を特定できそうです。

追記2

隣接する1同士をすべて連結部としてグラフと考え、networkxとかで最大連結部分を取得するとか。これなら杭＝末端とかの把握も簡単でいいかもしれませんね。

追記3

二値画像だと思うことにして、opencvとかで最大の島を探すとかもありそう。（回りくどいですが）

Comments

[Ana_00]

回答ありがとうございます、斜め用の探索なども一度、追加してみます。参考になります。

[Ana_00]

networksなどは初めて聞きましたが、もしかしたら問題が解けるかもしれないので、見てみます！
回答ありがとうございます！

[jeanbiego]

思いつくまま書き散らしただけですが、どれかが参考になれば幸いです。