AOJ-2202 : X-Ray Screening System

X-Ray Screening System | Aizu Online Judge

概要

航空機に乗る前の手荷物検査を行なうプログラムを作成する．手荷物の中身のデータが与えられるので，不審な品物が入っていないのか判定する．正しい品物は全て長方形の形をしていて，不審な品物は長方形とは非常に異なる形状をしている．品物は重なっているものもあるので，その場合は前にある品物が表示される．

解法

それぞれの品物の座標の最大値・最小値を読み取る．正しい品物は長方形の形をしているため，それぞれの品物の縦横の最大値・最小値を用いて，長方形を描く事が出来る．つまり，品物が長方形ではなければ，元の形と異なった形になります．

次に，品物は重なっている物があるため，それぞれの品物の重なり方を全て試してみる．品物の重なり方は品物の全ての組み合わせを列挙すれば良いので，C++ の next_permutation を使うと楽です．

このときに読み取った手荷物の状態と同じ状態が作れれば，"SAFE"を出力すればよい．品物の種類は最大で７種類までなので，全探索しても問題ない．

ソースコード

// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2002

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<climits>
#include<ctime>
#include<cstring>
#include<numeric>

#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;

using namespace std;

struct rect {
	int min_w, max_w;
	int min_h, max_h;
	void update(int w, int h) {
		min_w = min(min_w, w); max_w = max(max_w, w);
		min_h = min(min_h, h); max_h = max(max_h, h);
	}
};

int h, w;
vector<vector<char>> bag;
vector<vector<char>> tmp;
vector<char> layer;	
map<char, rect> rects;

void fill_rect(char type) {
	rect rt = rects[type];
	for(int y = rt.min_h; y <= rt.max_h; ++y) {
		for(int x = rt.min_w; x <= rt.max_w; ++x) {
			tmp[y][x] = type;
		}
	}
	return;
}

bool is_safe() {
	rep(y, h) {
		rep(x, w) {
			if(tmp[y][x] != bag[y][x]) return false;
		}
	}
	return true;
}

int main() {
	int T;
	cin >> T;
	rep(i, T) {
		cin >> h >> w;
		bag.assign(h, vector<char>(w, '.'));
		rects.clear(); layer.clear();
		rep(y, h) {
			rep(x, w) {
				cin >> bag[y][x];
				if(bag[y][x] == '.') continue;
				if(rects.count(bag[y][x]) == 0) {
					rects[bag[y][x]] = {x, x, y, y};
					layer.push_back(bag[y][x]);
				} else {
					rects[bag[y][x]].update(x, y);
				}
			}
		}

		bool ok = false;
		sort(ALL(layer));
		do {
			tmp = bag;
			rep(i, layer.size()) {
				fill_rect(layer[i]);
			}
			if(is_safe()) { ok = true; break; }
		} while(next_permutation(ALL(layer)));
		
		cout << ((ok) ? "SAFE" : "SUSPICIOUS") << endl;
	}
	return 0;
}