はじめに
今回は、X-Ray Screening System (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2002)という問題を解いてみました!ちょっと前は、この問題を見た瞬間に「うっ…」ってなってしまっていたのですが、これがさらっと解けるようになったのは進歩かもしれないですね!競プロの第一歩は実装への抵抗をなくすこと!これです。
どうやって解いたか
この問題、最初読んだ時は「うっ…」ってなってしまいますよね。その一番の原因はSample Inputの4つめにあると思います。
.......... .DDDDDD... .DDDDCCC.. .DDDDCCC.. ADDDDCCC.. AAA..CCC.. AAABBBBC.. AAABBBB... ..BBBBB... ..........
これ、一見すると全部長方形に見えますよね。でも違います!もし全部長方形だとしたら…Dの手前にCがあって、Cの手前にBがあって、Bの手前にAがあって、Aの手前にD……ってあやややや!まるでエッシャー *1 みたいなことになってしまいます!問題文の条件から、このように位置がねじれていることはないので、これは SUSPICIOUS
です!これは一大スクープの予感がします!
これで混乱してしまいます。この問題はどうやったら解いたらいいのか!でも、落ち着いてください。物体にはx, y, z座標が決まっています。手前-奥方向はx座標です。つまりですね、どれかは絶対一番手前にあるはずなんです。一番手前にあるってことは、見るからに長方形じゃないといけませんよね。こうして手前にあるものから順に処理していけばいいのです。では部分部分にわけてより詳しく見ていきます。
ワイルドカードを使って手前から見ていく
この例を使って説明していきます
.......... .DDDDCCC.. .DDDDCCC.. .DDDDCCC.. ADDDDCCC.. AAA..CCC.. AAABBBBC.. AAABBBB... ..BBBBB... ..........
- まず最初は一番手前のものを見つけます。先ほど言ったように、どれかは必ず一番手前にあるはずです。一番手前にあるものは全貌が見えますよね?この段階で長方形になっているものがなかったら…それはもう
SUSPICIOUS
です!この例ではDが長方形ですね。つまりこれが一番手前にあると仮定できます。 - 一番手前にある長方形の物体を見つけたとしましょう。長方形かどうかの判定方法はまた後に述べます。じゃあこの長方形は処理してしまったので、ワイルドカード
*
に置き換えます。以降、この*
は.
も含めた好きな文字として扱っていいわけです。下のようになります。
.......... .****CCC.. .****CCC.. .****CCC.. A****CCC.. AAA..CCC.. AAABBBBC.. AAABBBB... ..BBBBB... ..........
- じゃあ次に、
*
を適当に置き換えて長方形になるものを探すと…例として下のようにうまく置き換えたらAが長方形になりますね。
.......... .....CCC.. .....CCC.. .....CCC.. AAA..CCC.. AAA..CCC.. AAABBBBC.. AAABBBB... ..BBBBB... ..........
- じゃあAは長方形の可能性があるのでクリアです。今度はAを*に置き換えて…
.......... .****CCC.. .****CCC.. .****CCC.. *****CCC.. ***..CCC.. ***BBBBC.. ***BBBB... ..BBBBB... ..........
- これですべて長方形にできるかどうか確かめれえばいいわけです。この例だと次はBですかね。
長方形の判定
例えば、Aが長方形かどうか判定するには、Aが登場する一番上、一番下、一番左、一番右を特定し、それで囲まれる長方形の中がすべてAまたはワイルドカード *
であることを確認すればいいわけですね。
static boolean isFilled(char[][] c, int h, int w, int target, int top, int bottom, int left, int right){ for(int i = top; i <= bottom; i++){ for(int j = left; j <= right; j++){ if(c[i][j] != target && c[i][j] != '*'){ return false; } } } return true; }
最終的に
これを続けていって、
- すべてのマスが
.
または*
で埋められる→SAFE - ワイルドカード
*
を駆使しても長方形にならないものが残った→SUSPICIOUS
です。基本的に、奥にあるものほど(ワイルドカードが増えるので)長方形判定は緩くなるのですが、そうやって後回し後回しにしても長方形にならなかったら、これはSUSPICIOUSですね。
あと注意としては、最後のSampleにもあるように、同じアルファベットは必ずしも隣接して登場するとは限りません。判定ミスがないように全部調べあげてください。
ソースコード全体
class Main extends MyUtil{ public static void main(String[] args) throws Exception{ // 入力に関しては自作のくらすを使いました。 int n = readInt(); for (int i = 0; i < n; i++) { int h = readIntMap(0); int w = readIntMap(1); char[][] c = new char[h][]; for (int j = 0; j < h; j++) { c[j] = readLine().toCharArray(); } if(solve(c, h, w)){ System.out.println("SAFE"); }else{ System.out.println("SUSPICIOUS"); } } } static boolean solve(char[][] c, int h, int w){ while(checkThisTurn(c, h, w)); // 全部消えたかチェック for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if(c[i][j] != '.' && c[i][j] != '*'){ return false; } } } return true; } static boolean checkThisTurn(char[][] c, int h, int w){ HashSet<Character> checked = new HashSet<Character>(); checked.add('.'); checked.add('*'); for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if(!checked.contains(c[i][j])){ if(checkRect(c, h, w, c[i][j])){ // 長方形だったら return true; } } // このターンでは確認済み checked.add(c[i][j]); } } return false; } static boolean checkRect(char[][] c, int h, int w, char target){ int top = h, bottom = 0, left = w, right = 0; // 上下左右の端を確認 for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if(c[i][j] == target){ top = Math.min(top, i); bottom = Math.max(bottom, i); left = Math.min(left, j); right = Math.max(right, j); } } } // そこが埋まっているか確認 if(isFilled(c, h, w, target, top, bottom, left, right)){ //埋まってる for(int i = top; i <= bottom; i++){ for(int j = left; j <= right; j++){ // 次からワイルとカードとして扱える c[i][j] = '*'; } } return true; }else{ //埋まってない return false; } } static boolean isFilled(char[][] c, int h, int w, int target, int top, int bottom, int left, int right){ for(int i = top; i <= bottom; i++){ for(int j = left; j <= right; j++){ if(c[i][j] != target && c[i][j] != '*'){ return false; } } } return true; } }