ICPC模擬国内予選2006 C - X-Ray Screening System

問題概要

ちょっとまとめるのが面倒なので，問題文原文を見てください (手抜き)

解法概要

長方形の領域になっている部分を貪欲に取り除いていく．取り除かれた長方形の領域は，次の長方形を探す際に長方形の領域として使って良い (使わなくても良い)．

長方形領域の判定は，左上と右下の取りうる座標の組み合わせを全通り試すとそれだけで$ O(n^4) $となりTLEしてしまう．そこでこの問題では同じ文字が複数の長方形を形成することはないということを利用する．ある文字cの領域が長方形かどうかを確かめるには，cが置かれている最も左上の座標と最も右下の座標を調べ，それらの座標によって作られる長方形領域が文字cまたはすでに取り除かれた長方形の文字で満たされているかをチェックすればソースコード

#include<iostream>
#include<utility>
#include<vector>
#include<map>
#include<set>

using namespace std;

map<char, bool> is_removed;
int h,w;
char c = '*';

bool is_rectangle(int si, int sj, int gi, int gj, char c, string s[]){
    for(int i=0;i<h;++i){
        for(int j=0;j<w;++j){
            if(si <= i && i <= gi && sj <= j && j <= gj){
                if(s[i][j] != c && !is_removed[s[i][j]]){
                    return false;
                }
            }else{
                if(s[i][j] == c) return false;
            }
        }
    }
    return true;
}

string solve(string s[]){
    set<char> st;
    for(int i=0;i<h;++i){
        for(int j=0;j<w;++j){
            if(s[i][j] != '.') st.insert(s[i][j]);
        }
    }
    int baggage_cnt = (int)st.size();
    if(!baggage_cnt) return "SAFE";

    bool change = true;
    while(change){
        change = false;
        for(char c: st){
            if(is_removed[c]) continue;
            int si = INT_MAX, sj = INT_MAX, gi = -1, gj = -1;
            for(int i=0;i<h;++i){
                for(int j=0;j<w;++j){
                    if(s[i][j] == c){
                        si = min(i, si);
                        sj = min(j, sj);
                        gi = max(i, gi);
                        gj = max(j, gj);
                    }
                }
            }
            if(gi == -1) continue;

            if(is_rectangle(si, sj, gi, gj, c, s)){
                is_removed[c] = true;
                change = true;
                baggage_cnt--;
                if(!baggage_cnt) return "SAFE";
            }
        }
    }
    return "SUSPICIOUS";
}

int main() {
    int t;
    cin >> t;

    for(int tt=0;tt<t;++tt){
        cin >> h >> w;
        string s[h];
        for(int i=0;i<h;++i) cin >> s[i];
        is_removed.clear();
        cout << solve(s) << endl;
    }
}

感想

AOJはまだ6問しか解いていないが実装が重くて他オンラインジャッジとは違った感じ． とりあえず300点問題を解いているが，点数に対する難易度感もよくわかってない．