ことさら−古都プログラマーの更級日記

京都でお寺を回りながら御朱印集めをしていたエンジニアのブログ。おもに技術的なはなしとか日常的なはなし。たまにカメラの話や競馬の話も書きます。

AOJ 2002: X-Ray Screening System

はじめに

今回は、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;
    }
}