SRM505 div1 easy
二つの列に一箇所でも共通点があれば片方でしか分かっていない情報も分かるようななる。
行についても同様。
#include <string> #include <vector> using namespace std; class RectangleArea { public: int h,w; vector<string> vs; void check() { for(int i=0;i<h;i++) for(int j=i+1;j<h;j++) { int k; for(k=0;k<w;k++) if(vs[i][k]=='Y' && vs[j][k]=='Y') break; if(k<w) for(int k=0;k<w;k++) if(vs[i][k]=='Y' || vs[j][k]=='Y') vs[i][k]=vs[j][k]='Y'; } for(int i=0;i<w;i++) for(int j=i+1;j<w;j++) { int k; for(k=0;k<h;k++) if(vs[k][i]=='Y' && vs[k][j]=='Y') break; if(k<h) for(int k=0;k<h;k++) if(vs[k][i]=='Y' || vs[k][j]=='Y') vs[k][i]=vs[k][j]='Y'; } for(int i=0;i<h;i++) for(int j=i+1;j<h;j++) { int k; for(k=0;k<w;k++) if(vs[i][k]=='Y' && vs[j][k]=='Y') break; if(k<w) for(int k=0;k<w;k++) if(vs[i][k]=='Y' || vs[j][k]=='Y') vs[i][k]=vs[j][k]='Y'; } for(int i=0;i<w;i++) for(int j=i+1;j<w;j++) { int k; for(k=0;k<h;k++) if(vs[k][i]=='Y' && vs[k][j]=='Y') break; if(k<h) for(int k=0;k<h;k++) if(vs[k][i]=='Y' || vs[k][j]=='Y') vs[k][i]=vs[k][j]='Y'; } return; } int minimumQueries(vector <string> known) { vs=known; h=vs.size(),w=vs[0].size(); check(); int ans=0; while(1) { bool end=true; int y,x; for(int i=0;i<h;i++) for(int j=0;j<w;j++) if(vs[i][j]=='N') { y=i,x=j; end=false; break; } if(end) break; ans++; vs[y][x]='Y'; check(); } return ans; } };