Python
 Computer >> コンピューター >  >> プログラミング >> Python

Pythonで0で埋められたすべての長方形を検索する

バイナリ2Dマトリックスがあるとすると、0で埋められたすべての長方形の始点と終点を見つける必要があります。長方形は分離されており、互いに接触していないことを覚えておく必要がありますが、配列の境界に接触することはできます。要素が1つしかない長方形も可能です。

したがって、入力が-

のような場合
1 0 1 1 1 0 1
1 1 0 1 1 1 1
1 0 1 1 0 0 1
1 0 1 1 0 0 1
1 0 1 1 0 1 1
1 0 1 0 0 0 0
1 1 1 0 0 0 1
1 0 1 1 1 0 1

その場合、出力は[[0、1、0、1]、[0、5、0、5]、[1、2、1、2]、[2、3、2、4]、[3、1]になります。 、5、1]、[3、4、6、5]、[5、3、6、5]、[7、1、7、1]、[7、5、7、5]]

これを解決するには、次の手順に従います-

  • 関数find_rect（）を定義します。これにはi、j、a、output、indexが必要です
  • x：=行数
  • y：=列数
  • flag_col：=0
  • flag_row：=0
  • iからxの範囲のmについては、
    • a [m、j]が1と同じ場合、
      • flag_row：=1
      • 休憩
    • a [m、j]が5と同じ場合、
      • 何もしない
    • jからyの範囲のnについては、
      • a [m、n]が1と同じ場合、
        • flag_col：=1
        • 休憩
      • a [m、n]：=5
    • flag_rowが1と同じ場合、
      • 出力の最後にm-1を挿入[インデックス]
    • それ以外の場合、
      • output[index]の最後にmを挿入します
    • flag_colが1と同じ場合、
      • output[index]の最後にn-1を挿入します
    • それ以外の場合、
      • output[index]の最後にnを挿入します
  • メインの方法から、次の手順を実行します-
  • n：=aのサイズ
  • op：=新しいリスト
  • idx：=-1
  • 0からnの範囲のiについては、
    • 範囲0からa[0]のサイズのjの場合、実行
      • a [i、j]が0と同じ場合、
        • [i、j]をopに挿入
        • idx：=idx + 1
        • find_rect（i、j、a、op、idx）
  • 表示操作
サンプルコード

理解を深めるために、次の実装を見てみましょう-

def find_rect(i,j,a,output,index):
   x = len(a)
   y = len(a[0])
   flag_col = 0
   flag_row = 0
   for m in range(i,x):
      if a[m][j] == 1:
         flag_row = 1
         break
      if a[m][j] == 5:
         pass
      for n in range(j, y):
         if a[m][n] == 1:
            flag_col = 1
            break
         a[m][n] = 5
   if flag_row == 1:
      output[index].append( m-1)
   else:
      output[index].append(m)
   if flag_col == 1:
      output[index].append(n-1)
   else:
      output[index].append(n)
def get_coord(a):
   n = len(a)
   op = []
   idx = -1
   for i in range(0,n):
      for j in range(0, len(a[0])):
         if a[i][j] == 0:
         op.append([i, j])
         idx = idx + 1
         find_rect(i, j, a, op, idx)
   print (op)
tests = [[1, 0, 1, 1, 1, 0, 1],
         [1, 1, 0, 1, 1, 1, 1],
         [1, 1, 1, 0, 0, 1, 1],
         [1, 0, 1, 1, 0, 0, 1],
         [1, 0, 1, 1, 0, 1, 1],
         [1, 0, 1, 0, 0, 0, 0],
         [1, 1, 1, 0, 0, 0, 1],
         [1, 0, 1, 1, 1, 0, 1]]
get_coord(tests)

入力

[[1, 0, 1, 1, 1, 0, 1],
[1, 1, 0, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 1, 1],
[1, 0, 1, 1, 0, 0, 1],
[1, 0, 1, 1, 0, 1, 1],
[1, 0, 1, 0, 0, 0, 0],
[1, 1, 1, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 1]]

出力

[[0, 1, 0, 1], [0, 5, 0, 5], [1, 2, 1, 2], [2, 3, 2, 4], [3, 1, 5, 1], [3, 4, 6, 5], [5, 3, 6, 5], [7, 1, 7, 1], [7, 5, 7, 5]]

  1. Pythonでn個のノードを持つすべての単純な無向グラフのコストの合計を見つけるプログラム

    n個のノードを持つ無向グラフGがあるとします。ここで、単純な無向グラフのコストがそのノードのコストの合計であると考えてください。また、ノードのコストはD ^ kです。ここで、Dはその次数です。これで、n個とk個の値ができました。 n個のノードを持つすべての可能な単純な無向グラフのコストの合計を見つける必要があります。結果は非常に大きくなる可能性があるため、1005060097を法として結果を返します。 したがって、入力がn =3 k =2の場合、出力は36になります。これは、3つのノードを持つ8つの単純なグラフがあるためです。 エッジが3つしかない1つのグラフで、コストは2 ^ 2 + 2

  2. Pythonで2つの長方形で覆われた総面積を見つけるプログラム

    2D平面内の2つの直線状の長方形でカバーされる総面積を求めたいとします。ここで、各長方形は、図に示すように、左下隅と右上隅によって定義されます。 これを解決するには、次の手順に従います- width_1：=| C-A |、height_1：=| D-B | width_2：=| G-E |、height_2：=| H-F | area：=width_1 * height_1 + width_2 * height_2 （G D）または（H