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; }