BOJ-20061-モノドミノ2


質問する


https://www.acmicpc.net/problem/14499

問題は長いですね.

に答える


アイデア


青い格子と緑の格子の動作原理はブロックの蹴り方が違うだけで、まったく同じです.積み木が蹴り出す方向を統一し、代入された足を回転させると、ボールごとに2つの状況があります.

このように与えられた問題を考えると、入力を変更する関数と
一つの問題ルールを集中的に表すクラスだけでいいようです.
行または列がタイルで満たされると、浅いセルに塊がある場合が同時に発生する可能性があります.この場合、行や列がタイルで満たされていない場合、点数を得る過程がすべて行われた後、軟格子に塊がある場合を処理すべきである.
実装する必要がある機能は次のとおりです.
1.ブレークで停止します.
2.行が満たされている場合は、それを加算して、行を削除してから上に引くことができます.
3.白い格子がブロックだらけの場合、白い格子にブロックがない場合に推進する機能
1->2回繰り返し、変化なし->3回繰り返し->1回繰り返し
これでいい
改めて考えてみると、2と3を繰り返すことなく、そのまま2を使ってから3をしても大丈夫です.分類事例
  • 白い格子xはx->を完成させてスタックを続ければよい.
  • スペースx完了o->完了した行を削除し、1行押すと
  • になります.
  • 白い格子oはx->白い格子を押しのけるだけで済みます.
  • の白い格子oを完成o->完成後、後ろに白い格子があれば押し上げることができます.
  • どうせ2回やった後に1、3を区別して後押しをすればいいので、繰り返す必要はありません.白い格子の線も完成するはずがなく、例外はありません.
    したがって、実行順序は1->2->3->
    繰り返すだけでいい.

    インプリメンテーション


    まず、入力を返す関数を作成します.
    x,yは4 x 4で、箱の中で90度回転したのと同じです.
    t=1の場合、t=1
    t=2の場合、t=3
    t=3の場合、t=2.
    def rotate(x,y,t):
        if t == 1 or t == 2:
            nx, ny = y, 3-x
        else:
            nx, ny = y, 3-x-1
        nt = [1,3,2][t-1]
        return nt,nx,ny
    t=3で90度回転すると、座標は横になっているブロックの左側ではなく、右側のブロックを指すので、y座標でさらに1を減算します.同様に重要なのは、一つ一つ実現し、確認する過程である.
    #input
    2 3 0
    3 2 2
    3 2 3
    
    #output
    (3, 0, 0)
    (2, 2, 0)
    (2, 3, 0)

    よかった.
    次にクラスを組織し、まず次のブロックの部分を実現します.
    class Board:
       def __init__(self):
           self.board = [[0]*4 for _ in range(6)]
           self.score = 0
    
       def putblock(self,t,x,y):
           if t == 1:
               check = [(1,0)]
           elif t == 2:
               check = [(1,0),(1,1)]
           else:
               check = [(2,0),(1,0)]
               
           nx, ny = 0, y
           flag = True
           while flag and nx < 6:
               for _ in check:
                   if 6 <= nx+_[0] or self.board[nx+_[0]][ny+_[1]]:
                       flag = False
                       break
               else:
                   nx += 1
           for _ in check:
               self.board[nx+_[0]-1][ny+_[1]] = 1
    
           pprint(self.board)
    汚くてたまらない.
    チェックリストを作成し、カーソルより1つ低い欄でナビゲートさせ、チェックリストが1と出会ったり探索したりする範囲が地面を突破する前にnxを1つずつ育成し、チェックが1と出会ったら停止したカフェで黒板を埋めておけばいい、チェックが地面を突破したらその位置で停止して埋め尽くせばいいことを確認します.
    # input
    4
    2 3 0
    3 2 2
    3 2 3
    3 3 0
    
    #output
    [[0, 0, 0, 0],
     [0, 0, 0, 0],
     [0, 0, 0, 0],
     [0, 0, 0, 0],
     [0, 0, 0, 0],
     [1, 1, 0, 0]]
     
    [[0, 0, 0, 0],
     [0, 0, 0, 0],
     [0, 0, 0, 0],
     [0, 0, 0, 0],
     [0, 0, 1, 0],
     [1, 1, 1, 0]]
     
    [[0, 0, 0, 0],
     [0, 0, 0, 0],
     [0, 0, 0, 0],
     [0, 0, 0, 0],
     [0, 0, 1, 1],
     [1, 1, 1, 1]]
     
    [[0, 0, 0, 0],
     [0, 0, 0, 0],
     [0, 0, 0, 0],
     [1, 0, 0, 0],
     [1, 0, 1, 1],
     [1, 1, 1, 1]]
    
    よかった!
    ローが満たされている場合は、ローを加算、消去して上に移動できます.
    
        def scoring(self):
           for idx in range(2,6):
               if all(self.board[idx]):
                   self.score += 1
                   del self.board[idx]
                   self.board.insert(0, [0,0,0,0])
    
    実装の問題を考慮せずに、直接消去し、上に空の行を挿入します.
    白欄にブロックを埋めるときは、白欄にブロックがないときまで行を押すことができます.
        def regul(self):
           for idx in range(0,2):
               if any(self.board[idx]):
                   del self.board[-1]
                   self.board.insert(0, [0, 0, 0, 0])
    
    同様に、最後の行を削除し、前に空の行を挿入します.
    
        def ordering(self,t,x,y):
           self.putblock(t,x,y)
           self.scoring()
           self.regul()
    
       def printing(self):
           cnt = 0
           for idx in range(2, 6):
               cnt += sum(self.board[idx])
           return self.score, cnt
    
    最後に実装された関数は、順番に実行される関数です.
    スコアと1つの数の印刷関数を収集
    N = int(readline().rstrip())
    order = [list(map(int,readline().split())) for _ in range(N)]
    
    A = Board()
    B = Board()
    
    for t,x,y in order:
       nt,nx,ny = (rotate(x,y,t))
       A.ordering(t,x,y)
       B.ordering(nt,nx,ny)
    
    A_s, A_c = A.printing()
    B_s, B_c = B.printing()
    print(A_s+B_s)
    print(A_c+B_c)
    
    主な部分...AとBボードを作成することで、Aは元のコマンドをBに入れ、Bは回転を考慮したすべての新しいコマンドを印刷した値を加算して出力し、終了します.

    結果



    やっぱり1つずつ編み出せば実現できるんだなぁ…
    逆にdpや数学は難しすぎます
    前の問題よりもっと難しくておもしろい!