猫でもわかるWebプログラミングと副業

本業エンジニアリングマネージャー。副業Webエンジニア。Web開発のヒントや、副業、日常生活のことを書きます。

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;
    }
}