結果

問題 No.2958 Placing Many L-s
ユーザー navel_tos
提出日時 2025-01-11 20:14:10
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 242 ms / 2,000 ms
コード長 4,663 bytes
コンパイル時間 530 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 80,384 KB
最終ジャッジ日時 2025-01-11 20:14:21
合計ジャッジ時間 9,413 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder2958 Placing Many L-s

#実験コードを書く
def brute(H, W):
    def make_valid():
        block = []
        for G in ([[1, 1, 1], [x, 0, x ^ 1], [0, 0, 0]] for x in range(2)):
            for _ in range(4):
                G = [[G[h][~ w] for h in range(3)] for w in range(3)]
                for i, (h, w) in enumerate([(h, w) for h in range(3) for w in range(3)]):
                    if G[h][w] == 1:
                        break
                H = []
                for x in range(3):
                    for y in range(3):
                        if G[x][y] == 1:
                            H.append((x - h, y - w))
                block.append(H)
        return block

    block = make_valid()
            

    #非再帰DFSで全列挙  左上詰で置いたときに最初の空きマスが(h, w)で、block[t]を置く予定
    G = [[0] * W for _ in range(H)]
    stack = [(0, 0, t) for t in range(8)]
    d = 0  #再帰の深さ
    while stack:
        h, w, t = stack.pop()

        if h >= 0:  #行きがけの処理
            #1. 実際に置けるか判定。置けないならcontinue  置けるなら実際に配置
            if not all( (x := h + p) in range(H) and (y := w + q) in range(W) and
                        G[x][y] == 0 for p, q in block[t] ):
                continue
            d += 1
            stack.append((~ h, w, t))
            for p, q in block[t]:
                assert G[ x := h + p ][ y := w + q ] == 0
                G[x][y] = d

            #2. 次の探索へ
            a = h * W + w
            for a in range(a + 1, H * W + 1):
                if a == H * W:
                    break
                x, y = a // W, a % W
                if G[x][y] == 0:
                    break
            if a == H * W:  #完全に置き切れた場合
                assert all( G[h][w] > 0 for h in range(H) for w in range(W) ), str(G)
                return G
            x, y = a // W, a % W
            for u in range(8):
                stack.append((x, y, u))


        else:  #帰りがけの処理
            h = ~ h
            #1. 既に置いた石を除去
            for p, q in block[t]:
                assert G[ x := h + p ][ y := w + q ] == d
                G[x][y] = 0
            d -= 1
    else:  #だめでした
        return G



#H, Wのうち、Hが偶数になるように適宜変更する。
#H ≡ 0 mod 8: W >= 2で常に可能。(8, 2), (8, 3)の構築を並べる
#H ≡ 4 mod 8: Wが偶数なら可能。(4, 2)を並べる
#H ≡ 2, 6 mod 8: Wが4の倍数なら可能。(W, H)を90度回転させる
#結局 (4, 2), (8, 2), (8, 3)を使って構築すればよいと分かる
tiles = [[None] * 9 for _ in range(9)]
for h, w in [(4, 2), (8, 2), (8, 3)]:
    tiles[h][w] = brute(h, w)

def rotate(G):
    if len(G) == 0:
        return []
    else:
        return [[G[h][~ w] for h in range( len(G) )] for w in range( len(G[0]) )]

def solve(H, W):
    if H & 1 == W & 1 == 1:
        return []
    if H & 1:
        return rotate( solve(W, H) )

    #1. H ≡ 0 mod 8 を構築する
    if H % 8 == 0:
        if W == 1:
            return []
        G = [[0] * W for _ in range(H)]
        offset = 0  #既に置いた値
        for h in range(0, H, 8):
            if W & 1:  #(8, 3)構築を置く
                base = tiles[8][3]
                for x in range(8):
                    for y in range(3):
                        G[h + x][0 + y] = base[x][y] + offset
                offset += 6
            for w in range( (3 if W & 1 else 0), W - 1, 2 ):
                base = tiles[8][2]
                for x in range(8):
                    for y in range(2):
                        G[h + x][w + y] = base[x][y] + offset
                offset += 4
        return G

    #2. H ≡ 4 mod 8 を構築する
    if H % 8 == 4:
        if W & 1 == 1:
            return []
        G = [[0] * W for _ in range(H)]
        offset = 0
        base = tiles[4][2]
        for h in range(0, H, 4):
            for w in range(0, W, 2):
                for x in range(4):
                    for y in range(2):
                        G[h + x][w + y] = base[x][y] + offset
                offset += 2
        return G

    #3. H ≡ 2, 6 mod 8 を構築する
    if H % 8 in [2, 6]:
        return rotate( solve(W, H) ) if W % 4 == 0 else []
    return []
                
    
    
#実行  エスパーしたけどおもしろかった
for _ in range( T := int(input()) ):
    H, W = map(int, input().split())
    G = solve(H, W)
    if G == []:
        print(-1)
    else:
        print(H * W // 4)
        for h in range(H):
            print(*G[h])
0