SRM505 Div1Easy RectangleArea

http://community.topcoder.com/stat?c=problem_statement&pm=11400

ある長方形について頂点を含む4つの小長方形を考えると、このうち3つの面積がわかっている(Y)ならば残り1つの面積もわかる。これを繰り返すといずれ盤上の'Y'が増えなくなるため、小長方形の面積を質問する必要があり、その回数を調べる。
質問する小長方形はどれでもよさそうだが確証はない。

ケースが大きいとTLEするらしい。再帰部分が明らかに怪しいがいまいちわからない。改善中…
creepさんの記事などを参考にして通しました。TLE解では再帰時に頂点を全探索していたのでだが、実際には'N'→'Y'としたところに関係する場所しか変わらないので、に減らせるはず。結果として、全体では→に削減
creep06.hatenablog.com

改善後

#include <bits/stdc++.h>
using namespace std;

class RectangleArea {
public:
    int h,w;
    int board[51][51];
    int ret=0;
    // (sy,sx)を1頂点とした長方形について、穴埋め
    void greed(int sy,int sx){
        // 対角の座標で探索
        for(int y=0;y<h;y++){
            for(int x=0;x<w;x++){
                // 長方形でないので×
                if(sy==y||sx==x) continue;
                // 3つの小長方形の面積がわかっている
                if(board[sy][sx]+board[y][sx]+board[sy][x]+board[y][x]==3){
                    if(board[y][sx]==0){
                        board[y][sx]=1;
                        greed(y,sx);
                    }
                    if(board[sy][x]==0){
                        board[sy][x]=1;
                        greed(sy,x);
                    }
                    if(board[y][x]==0){
                        board[y][x]=1;
                        greed(y,x);
                    }
                }
            }
        }
    }
    
    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;
            }
        }
        // 面積がわかっているところを先に埋める
        for(int y=0;y<h;y++){
            for(int x=0;x<w;x++){
                if(board[y][x]==1){
                    greed(y,x);
                }
            }
        }
        // 質問しないといけないので実行する度に回数+1
        for(int y=0;y<h;y++){
            for(int x=0;x<w;x++){
                if(board[y][x]==0){
                    board[y][x]=1;
                    ret++;
                    greed(y,x);
                }
            }
        }
        return ret;
    }
};

改善前

#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(!end) break;
            }
            if(end) break;
        }
        return ret;
    }
};