AOJ 2002: X-Ray Screening System

問題

X-Ray Screening System | Aizu Online Judge

解法

それぞれの物体の四点を取って、その中に空白が入ってたらアウト。空白のある物体が存在しない時は上下関係を見て、矛盾があればアウト。

本当は、必ず1つは長方形が存在するはずなので、それを上手く使うと解ける。

コード

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int h = sc.nextInt();
            int w = sc.nextInt();

            char[][] result = new char[h][];
            for (int j = 0; j < result.length; j++) {
                String line = sc.next();
                result[j] = line.toCharArray();
            }

            Map<Character, Integer[]> map = new HashMap<Character, Integer[]>();
            HashMap<Character, ArrayList<Character>> under = new HashMap<Character, ArrayList<Character>>();
            for (int j = 0; j < result.length; j++) {
                for (int k = 0; k < result[j].length; k++) {
                    if (result[j][k] != '.') {
                        if (map.get(result[j][k]) == null) {
                            Integer[] put = { j, k, j, k };
                            map.put(result[j][k], put);
                            under.put(result[j][k], new ArrayList<Character>());
                        } else {
                            Integer[] get = map.get(result[j][k]);
                            map.get(result[j][k])[0] = Math.min(get[0], j);
                            map.get(result[j][k])[1] = Math.min(get[1], k);
                            map.get(result[j][k])[2] = Math.max(get[2], j);
                            map.get(result[j][k])[3] = Math.max(get[3], k);
                        }
                    }
                }
            }

            boolean safe = true;

         check: for (Map.Entry<Character, Integer[]> entry : map.entrySet()) {
                char key = entry.getKey();
                Integer[] get = map.get(key);

                for (int j = get[0]; j <= get[2]; j++) {
                    for (int k = get[1]; k <= get[3]; k++) {
                        if (result[j][k] == '.') {
                            // 明らかに長方形でない時
                            System.out.println("SUSPICIOUS");
                            safe = false;
                            break check;
                        } else if (result[j][k] != key) {
                            // 別の文字がかぶっている時
                            // keyの上にresult[j][k]
                            under.get(key).add(result[j][k]);
                        }
                    }
                }
            }

            if (!safe) {
                continue;
            }

         check: for (Map.Entry<Character, ArrayList<Character>> entry : under
                    .entrySet()) {
                Deque<Character> deque = new ArrayDeque<Character>();
                Deque<Character> checked = new ArrayDeque<Character>();

                for (Character character : entry.getValue()) {
                    deque.add(character);
                }
                while (!deque.isEmpty()) {
                    char poll = deque.poll();
                    checked.add(poll);
                    if (poll == entry.getKey()) {
                        // 明らかに長方形でない時
                        System.out.println("SUSPICIOUS");
                        safe = false;
                        break check;
                    }

                    for (Character character : under.get(poll)) {
                        if (!deque.contains(character)
                                && !checked.contains(character)) {
                            deque.add(character);
                        }
                    }
                }

            }

            if (safe) {
                System.out.println("SAFE");
            }
        }
        sc.close();
    }
}