読者です 読者をやめる 読者になる 読者になる

解いた問題のソースコードと解説など。


SRM 504 Div2 Hard Algrid

SRM 探索 シミュレーション
問題

http://apps.topcoder.com/stat?c=problem_statement&pm=11348&rd=14433

最初にH*Wの盤面が黒('B')か白('W')で塗られており、下の処理を経た局面がvector stringで与えられる。

For i = 0 to H-2:
    For j = 0 to W-2:
        //Get the current colors of cells (i,j) and (i,j+1)
        A = Color(i,j) , B = Color(i,j+1)

        If (A,B) == (White, White) Then:
             Do nothing.
        EndIf
        If (A,B) == (Black, White) Then: 
             Repaint cells (i+1,j) and (i+1,j+1) Black.
        EndIf
        If (A,B) == (White, Black) Then:
             Repaint cells (i+1,j) and (i+1,j+1) White.
        EndIf
        if (A,B) == (Black, Black) Then:
             Swap the colors in cells (i+1,j) and (i+1,j+1).
        EndIf
    EndFor
EndFor

この局面を生成するような辞書式最小の初期局面を返せ。なければ空のvector stringを返せ。

やりかた

上の処理は第一行目については影響が起きないのでそのままとできる。2行目以降はその前の行の処理を経て白か黒に塗られた場合は、もともと何色であったかは関係なくなるので辞書式で小さくなるように'B'で塗っておく。あとは、swapで色の移動が起きているなら、その色が元あった位置にもどせばいい。
処理後にかならず白や黒に塗られていなければならないマスがoutput上ではそうではない色で塗られていたら、NGなので空のvector stringを返す。

kusano_progさんの解答を参考にさせていただいた。提出したものもほとんど同じになってしまったのであちらをご参照ください。

しょげないでよBaby 眠れば治る