2002-X-Ray Screening System

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2002&lang=jp
考え方
全ての物質が長方形であると仮定して、その全ての順番について、与えられた図と一致するものがあるか確認する。
一致するものが無ければSUSPICIOUSで、一致するものが一つでもあればSAFE。
実装(C++)

#include <algorithm>
#include <vector>
#include <set>
#include <iostream>
#include <string>
using namespace std;
struct Rect{
	char name;
	int x1,x2,y1,y2;
};
bool operator<(const Rect &a,const Rect &b){
	return a.name<b.name;
}
int W,H;vector<string> MAP;
vector<string> TM;
inline void write(vector<string> &MAP,Rect &a){
	for(int x=a.x1;x<=a.x2;x++){
		for(int y=a.y1;y<=a.y2;y++){
			MAP[x][y]=a.name;
		}
	}
}
int main(){
	int T;cin>>T;

	for(;cin>>W>>H;){
		MAP=vector<string>(W);
		for(int i=0;i<W;i++)
			cin>>MAP[i];
		set<char> used;
		for(int x=0;x<W;x++){
			for(int y=0;y<H;y++){
				used.insert(MAP[x][y]);
			}
		}
		set<char>::iterator it=used.begin();
		vector<Rect> rect;
		while(it!=used.end()){
			Rect tmp;tmp.name=*it;tmp.x1=W+1;tmp.x2=-1;tmp.y1=H+1;tmp.y2=-1;
			for(int x=0;x<W;x++){
				for(int y=0;y<H;y++){
					if(MAP[x][y]==tmp.name){
						tmp.x1=min(tmp.x1,x);
						tmp.x2=max(tmp.x2,x);
						tmp.y1=min(tmp.y1,y);
						tmp.y2=max(tmp.y2,y);
					}
				}
			}
			rect.push_back(tmp);
			it++;
		}
		sort(rect.begin(),rect.end());
		TM=vector<string>(W);
		string tmp="";
		for(int i=0;i<H;i++)tmp+=" ";
		for(int i=0;i<W;i++)
			TM[i]=tmp;
		bool ok=false;
		bool hasdot=(used.find('.')!=used.end());
		do{
			if(hasdot&&rect.front().name!='.')continue;
			for(int i=0;i<(int)rect.size();i++){
				write(TM,rect[i]);
			}
			if(MAP==TM){
				ok=true;break;
			}
		}while(next_permutation(rect.begin(),rect.end()));
		if(ok){
			cout<<"SAFE"<<endl;
		}else{
			cout<<"SUSPICIOUS"<<endl;
		}
	}
	return 0;
}