AOJ2574 Magical Switches
問題概要
3行3N+1列のマップがあり，同じアルファベットについて，大文字と小文字の一方は全て壁であり，もう一方は通れる床である．左から右まで通れるようにしたいとき，壁にする大文字を全て出力せよ．解が複数あればどれか1つを出力せよ．解がない場合は -1 を出力せよ．
解法
愚直にやると 2^26 * 3 * N なので厳しい．3-SAT に変換して解く．条件が 2^3*N 項くらいになるので，計算量が O(3^8N) くらいになるが，適当に枝刈りすれば通る．オススメの枝刈りは，
・a or b or c の条件を見る際，既に前提として a or b or c が確定しているときは分岐しなくてよい
・a or b or c の条件を a or (not a and b) or (not a and not b c) に変換する
一応入力列をいい感じにソートしたりしたが，効果があったかどうかは知らない．
