問題
http://lealgorithm.blogspot.jp/2015/05/srm-658-div1-easy-oddeventree.htmlと同じだけど、x[i][j]='?'というのが許されている。(?だとOddとEvenどちらでも良い)
解法
Div1の方とほぼ同じ。まず対称性の確認とかx[i][i]=='O'だったらはじくとかやって、ワーシャルフロイドでx[i][j]+x[j][k]の偶奇とx[i][k]の偶奇の確認(もしx[i][k]が?だったら埋める)というのをやり、
それでもどこかに?があった場合はまずそれをOにしてみて矛盾する箇所がないか確認して、もし矛盾したらEにする、というのを行うとxから?がなくなるので後はDiv1と同じ構成方法を用いて構成する。
0 件のコメント:
コメントを投稿