つらねの日記

プログラムの進捗やゲームをプレイした感想などを書き連ねる日記。

AOJ 2002 - X-Ray Screening System

X-Ray Screening System | Aizu Online Judge

問題

危険物が含まれているかどうかをチェックする。与えられる情報は上から撮影したときの情報である。危険物は非矩形をしている。探索問題





注意した点

考え方として一番上面に在るものから除外していき、すべてが除外できた時にSAFEとする。

材質の数を数え、材質ごとのxyの最大値最小値を矩形の末端と仮定する。

                if (material.find(box[y][x]) == material.end()) {
                    material.insert({box[y][x], material.size()});
                    rects.push_back({XMAX, YMAX, 0, 0});
                }
                int idx = material[box[y][x]];
                rects[idx].l = min(rects[idx].l, x);
                rects[idx].u = min(rects[idx].u, y);
                rects[idx].r = max(rects[idx].r, x);
                rects[idx].d = max(rects[idx].d, y);

矩形の内部を探索し、矩形内にNONEが存在したとき、その材質を矩形でないと断定。SUSPICIOUSとしてチェックを終了する。

        if (!check_rects(rects)) {

またNONE以外の他の材質が存在した場合はただ乗っているだけという可能性があるのでここでは通す。

一番上に存在する物体を探す。

            for(auto it = material.begin(); it != material.end();++it) {
                if(!seen[it->second] && is_top(rects[it->second], it->first)){

見つかった場合にはその物体を取り除き、SOMEに置き換える。SOMEは全ての材質を許容する。
つまり矩形内に自分の材質あるいはSOMEが存在するときにその物体は一番上に存在するとする。

更新が発生しなかった時にループを終了させ、取り除くことができた物質の数によってSAFEあるいはSUSPICIOUSを出力する。