SRM 504 Div2 Hard Algrid
問題
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さんの解答を参考にさせていただいた。提出したものもほとんど同じになってしまったのであちらをご参照ください。
Get up! 明日のSUPER ST@R!