白駿解題1343ポリオミノ

boj 1343:ポリオミノ
質問アドレス:https://www.acmicpc.net/problem/1343
難易度:silver 5
1.問題の説明

民植は無限以下のポリ五味子を持っている.AAAAとBB

現在」.「X」と組んだ板が民植に与えられ、「X」をすべて覆い、重ならないようにしようとした.

このとき,"."五味子で覆うわけにはいかない.

ポリオミノですべて覆われた板紙を出力するプログラムを作成します.

最初の行は、最初の答えを辞書順に出力します.カバーがつかない場合は、-1を出力します.

実際には、より便利な出力例である.

XXXXXX -> AAAABB
XX.XX -> BB.BB
XXXX....XXX.....XX -> -1
X -> -1
XX.XXXXXXXXXX..XXXXXXXX...XXXXXX -> BB.AAAAAAAABB..AAAAAAAA...AAAABB

2.問題を解決する考え.
2つの解釈があります.

第1の方法は、貪欲放出法

を内蔵関数に置き換えることである.

第2の代替を使用しない実装+貪欲な放出方法

3.問題の処理方法

を使用して組み込み関数を置換
replace内蔵関数は、文字列の左側から、特定の文字列を必要な文字列で置き換えます.
欲張るならまずXXXXをAAAA残りのXXに変えてBBに変えればいい
Xが1つ以上の文字列に含まれている場合は、-1を出力します.

board = board.replace("XXXX", "AAAA")
board = board.replace("XX", "BB")

実施+greedy
論理の展開は大体以下の通りである.詳細はコードで理解できます.

文字列を入力します.

文字列が空になるまで、次の操作を繰り返します.

文字列の最初の文字をtempに格納します.

temp = . 繰り返し回数が0の場合はtemp

に戻る.

でなければ、上記の手順を繰り返し、tempに続きます.現れるまで繰り返す.

得られた

件に対してAAAA,BB変換動作を行った.

4.特別注意事項

内蔵関数の重要性

について

の第一感覚はgreedyの実現感覚を加えた

である.

.撮った部分がちょっと難しかったので途中でコードを書き直しました

最初はsplitを利用していましたが、そうすると.連続撮影...など.

5.コード実装

を使用して、コード

を置き換えます.

board = input()
board = board.replace("XXXX", "AAAA")
board = board.replace("XX", "BB")
if board.count('X') >= 1:
    board = -1
print(board)

実施+greedy

board = input()
ans = ''
counter = 0
def recur_get_first(x):
    global counter
    temp = x[0]
    if x[0] == '.' and counter == 0:
        return temp
    if x[0] == '.' and counter != 0:
        return ''
    if len(x) == 1:
        return temp
    else:
        counter += 1
        return temp + recur_get_first(x[1:])

while board:
    piece = ''
    counter = 0
    piece = recur_get_first(board)
    board = board[len(piece):]
    if piece == '.':
        ans += piece
    else:
        if len(piece) % 2 == 1:
            print(-1)
            exit(0)
        else:
            _rest = len(piece) % 4
            _quotient = _rest // 2
            ans += ('AAAA' * (len(piece) // 4) + 'BB' * _quotient)

print(ans)