Recursion

URL http://community.topcoder.com/stat?c=problem_statement&pm=11400 概略 小長方形を組み合わせた長方形の盤面が与えられる．小長方形の各々について，面積がわかっていればY，そうでなければNと表記される．質問をするたび，任意のNが1つYに変化する．最低で何回質問をすれば盤面全てをYに変えられるか． 方針 図の赤枠のように長方形をとる．このとき，頂点と接する4つの小長方形に着目する． 図より，このうち3つの面積がわかっている(Y)ならば，残り1つの面積もわかる．このような作業を繰り返すといずれ盤面のYが増えなくなるため，小長方形の面積を質問する必要がある． 質問する小長方形はどれでもよさそうだが確証はない． 追記1: ケースが大きいとTLEするらしい．再帰部分が明らかに怪しいがいまいちわからない．改善中… 追記2: creepさんなどの記事を参考にして通しました．TLE解では再帰時に頂点を全探索していたので $O(W^2H^2)$ だったが，実際にはN→Yとしたところに関係する場所しか変わらないので，$O(WH)$ に減らせるはず．結果として全体では $O(W^3H^3)$ → $O(W^2H^2)$ に削減． 改善後 [展開する] 改善前 #include <bits/stdc++.h> using namespace std; class RectangleArea { public: int h,w; int board[51][51]; int ret=-1; void greed(){ for(int y=0;y<h-1;y++){ for(int x=0;x<w-1;x++){ for(int dy=y;dy<h;dy++){ for(int dx=x;dx<w;dx++){ if(board[y][x]+board[y][dx]+board[dy][x]+board[dy][dx]==3){ board[y][x]=board[y][dx]=board[dy][x]=board[dy][dx]=1; greed(); } } } } } } int minimumQueries( vector <string> known ){ h=known.size(); w=known[0].size(); for(int y=0;y<h;y++){ for(int x=0;x<w;x++){ if(known[y][x]=='Y') board[y][x]=1; else board[y][x]=0; } } while(1){ ret++; greed(); bool end=true; for(int y=0;y<h;y++){ for(int x=0;x<w;x++){ if(board[y][x]==0){ board[y][x]=1; end=false; break; } } if(!