http://acm.pku.edu.cn/JudgeOnline/problem?id=1128
Код:
#include<iostream> #include<set> #include<vector> #include<string> using namespace std; enum { SIZ = 32, }; struct Node { int l,r,u,d; bool enable; set<int> ptr; set<int> next; }; Node tab[SIZ]; set<string> result; void init(){ for(int i=0;i<SIZ;i++){ tab[i].u=tab[i].l=tab[i].r=tab[i].d = -1; tab[i].enable = false; tab[i].ptr.clear(); tab[i].next.clear(); } } int h,w,m; int dat[SIZ][SIZ]; char buf[SIZ]; int top; void readIn(){ int i,j; char t; m = 0; for(i=0;i<h;i++){ for(j=0;j<w;j++){ cin>>t; if(t == '.'){ dat[i][j] = -1; continue; } t -= 'A'; if(m < t) m = t; dat[i][j] = t; tab[t].enable = true; if(tab[t].u == -1 || tab[t].u < i) tab[t].u = i; if(tab[t].d == -1 || tab[t].d > i) tab[t].d = i; if(tab[t].l == -1 || tab[t].l > j) tab[t].l = j; if(tab[t].r == -1 || tab[t].r < j) tab[t].r = j; } } m++; } void print_set(set<int> &s){ set<int>::iterator it; for(it=s.begin(); it!=s.end(); it++) cout<<" "<<char(*it + 'A'); cout<<endl; } void print(int cur){ cout<<"Number of "<<char(cur+'A')<<" depends: "<<tab[cur].ptr.size()<<endl; print_set(tab[cur].ptr); cout<<"Number of "<<char(cur+'A')<<" points: "<<tab[cur].next.size()<<endl; print_set(tab[cur].next); } void parse(){ int i,j; int l,h; for(i=0;i<m;i++){ if(tab[i].enable == false) continue; l = tab[i].d; h = tab[i].u; for(j=tab[i].l; j<= tab[i].r;j++){ if(dat[l][j] != i){ tab[i].ptr.insert(dat[l][j]); tab[dat[l][j]].next.insert(i); } if(dat[h][j] != i){ tab[i].ptr.insert(dat[h][j]); tab[dat[h][j]].next.insert(i); } } l = tab[i].l; h = tab[i].r; for(j=tab[i].d;j<=tab[i].u;j++){ if(dat[j][l] != i){ tab[i].ptr.insert(dat[j][l]); tab[dat[j][l]].next.insert(i); } if(dat[j][h]!=i){ tab[i].ptr.insert(dat[j][h]); tab[dat[j][h]].next.insert(i); } } } } void clear(int i, vector<int> &v){ set<int> & s = tab[i].next; for(set<int>::iterator it=s.begin(); it!=s.end(); it++){ v.push_back(*it); tab[*it].ptr.erase(i); } s.clear(); } void restore(int i, vector<int> &v){ set<int> &s = tab[i].next; int t; while(v.size()){ t = v.back(); v.pop_back(); s.insert(t); tab[t].ptr.insert(i); } } void trace(){ if(top == m){ buf[top] = 0; reverse(buf, buf+top); string s(buf); result.insert(s); reverse(buf, buf+top); return; } vector<int> v; for(int i=0; i<m;i++){ if(tab[i].enable == false || tab[i].ptr.size() != 0) continue; clear(i,v); tab[i].enable = false; buf[top++] = 'A' + i; trace(); --top; tab[i].enable = true; restore(i,v); } } int main(){ while(cin>>h>>w){ init(); readIn(); parse(); top = 0; trace(); for(set<string>::iterator it=result.begin(); it!=result.end();it++) cout<<(*it)<<endl; result.clear(); } return 0; }