ハッチングセグメント

問題の説明

テーブルの上のパズルの破片をゲームボードの空白に適当に置きたいです.ゲームボードとデスクトップは正方形のメッシュで、各セルのサイズは1 x 1です.次の規則に従って、テーブルの上のパズルブロックをゲームボードのスペースに埋めます.

一度に1つのセグメントを埋め込む

回転可能セグメント

セグメントを反転できません

新しいパズルブロックに隣接するスペースは、ゲームボードにはありません.

次に、パズルセグメントを塗りつぶす例を示します.

上図では、左側に現在のゲームボードの状態が表示され、右側にデスクトップのパズルの破片が表示されます.デスクトップ上のパズルブロックにも「上」、「下」、「左」、「右」が隣接していない場合、スペースはパズルの空白がないことを示します.すべてのパズルセグメントはグリッドにちょうど配置されており、エラーは配置されていません(たとえば、グリッドから離れたり、グリッドを越えたりします).
3番目、4番目、5番目のセグメントをグリッドに配置すると、以下のようにルールに違反しているため、不可能です.

3番破片4番破片を置く前に、上に隣接するスペースが表示されます.

5番ブロックの隣接セルにスペースが表示されます.

次はゲームボードにできるだけ多くの破片をルールに従って埋めます.

破片をできるだけ多く充填し、合計14格子を充填することができます.
現在のゲームボードの状態game_board,表の上のパズルブロックの状態tableがパラメータです.可能な限り多くのスペルブロックをルールに従って埋め込む場合は、solution関数を完了して、合計でどれだけのグリッドを埋め込むことができるかを返します.
せいげんじょうけん

3≦game_boardの行長≦50

game_boardの各列長=game_boardの行長

すなわち、ゲームボードは正方形メッシュである.

game_boardのすべての要素は0または1です.

0はスペース、1は埋め込まれたスペースです.

パズルセグメントのスペースを配置するには、1 x 1の正方形を最低1から最大6の接続に接続します.

tableの行長=game_boardの行長

tableの各列長=tableの行長

すなわち、表はgame_boardと同じ大きさの正方形メッシュである.

tableのすべての要素は0または1です.

0はスペース、1は断片化されたセルを表します.

パズルセグメントのサイズが1 x 1の正方形の最小接続1から最大接続6個.

game_board少なくとも1つのスペースが必要です.

tableは、1つ以上のブロックを含む必要があります.

I/O例
game_board
table
result
[[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]]
[[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]]
14
[[0,0,0],[1,1,0],[1,1,1]]
[[1,1,1],[1,0,0],[0,0,0]]
0
I/O例説明
I/O例#1
入力形式は次のとおりです.問題の例:

I/O例#2
ブロックを回転させることはできますが、ブロックを反転させることはできません.

私の答え

まだ初級レベルに達していない私は問題を解くかもしれません...理解できなかったので、後でDFSを勉強してから挑戦するつもりです.

他人を解く

import copy

def dfs(graph, x, y, position, n, num):
    dic = {0:[-1, 0], 1:[0, 1], 2:[1, 0], 3:[0, -1]}
    ret = [position]
    for i in range(4):
        nx = x + dic[i][0]
        ny = y + dic[i][1]
        if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] == num:
            graph[nx][ny] = 2
            ret = ret + dfs(graph, nx, ny, [position[0]+dic[i][0], position[1]+dic[i][1]], n, num)
    
    return ret
        
def rotate(lst):
    n = len(lst)
    ret = [[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            ret[j][n-1-i] = lst[i][j]
    
    return ret

def solution(game_board, table):
    answer = 0
    game_board_copy = copy.deepcopy(game_board)
    
    n = len(game_board)
    block = []
    for i in range(n):
        for j in range(n):
            if game_board_copy[i][j] == 0:
                game_board_copy[i][j] = 2
                result = dfs(game_board_copy, i, j, [0, 0], n, 0)[1:]
                block.append(result)
                
    for r in range(4):
        table = rotate(table)
        table_rotate_copy = copy.deepcopy(table)
        for i in range(n):
            for j in range(n):
                if table_rotate_copy[i][j] == 1:
                    table_rotate_copy[i][j] = 2
                    result = dfs(table_rotate_copy, i, j, [0, 0], n, 1)[1:]
                    if result in block:
                        block.pop(block.index(result))
                        answer += (len(result) + 1)
                        table = copy.deepcopy(table_rotate_copy)
                        
                    else:
                        table_rotate_copy = copy.deepcopy(table)
    return answer