WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM575 Div1 Hard "TheTilesDivOne"

問題

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

Div2 Hardと同じ

制約

1 <= チェスボードの高さ <= 47
1 <= チェスボードの幅 <= 47


解法

コチラを参考にしました。m(_ _)m
TopCoder SRM 575 Div1 Hard TheTilesDivOne - kmjp's blog

蟻本のP179のコラムもヒントになります。

白マスを奇数偶数にわけるという発想がでなかった!残念!
黒マスを示す頂点に一度しか流さないようにするために、
黒マス(使用前)→黒マス(使用後)とする必要があったのか。

いやこれいらないよな?と思って黒マス頂点1つで実装したら、
見事にSample0でWAになりました。


ソースコード

class MaxFlow{
public:
    MaxFlow( int max_n );
    ~MaxFlow();
    int get( int s, int t );
    void addEdge( int from, int to, int cap );
    void printGraph();

private:
    int dfs( int v, int t, int cap );
    struct Edge{ int to, cap, rev; }; 
    int max_n;
    vector<Edge>* G;
    bool* use;
};

class TheTilesDivOne {
public:
    int find(vector <string> board){
        int H = board.size();
        int W = board[0].length();
        int offset = H * W;
        int S = 2 * H * W;
        int T = 2 * H * W + 1;
        MaxFlow mf( 2 * H * W + 2 );

        // S -> 奇数の白マス
        for( int y = 0; y < H; y++ ){
            for( int x = 0; x < W; x++ ){
                if( x % 2 == 0 || (x + y) % 2 == 0 ) continue;
                if( board[y][x] == 'X' ) continue;
                int id = y * W + x;
                mf.addEdge( S, id, 1 );
            }
        }

        int dx[] = { 0, 0, -1, 1 };
        int dy[] = { -1, 1, 0, 0 };
        // 奇数の白マス -> 黒マス
        for( int y = 0; y < H; y++ ){
            for( int x = 0; x < W; x++ ){
                if( x % 2 == 0 || (x + y) % 2 == 0 ) continue;
                if( board[y][x] == 'X' ) continue;
                int wid = y * W + x;
                for( int d = 0; d < 4; d++ ){
                    int bx = x + dx[d], by = y + dy[d];
                    if( 0 <= bx && bx < W && 0 <= by && by < H && board[by][bx] == '.' ){
                        int bid = by * W + bx;
                        mf.addEdge( wid, bid, 1 );
                    }
                }
            }
        }

        // 黒マス(使用前) -> 黒マス(使用後)
        for( int y = 0; y < H; y++ ){
            for( int x = 0; x < W; x++ ){
                if( (x + y) % 2 ) continue;
                if( board[y][x] == 'X' ) continue;
                int bid = y * W + x;
                mf.addEdge( bid, bid + offset, 1 );
            }
        }

        // 黒マス(使用後) -> 偶数の白マス
        for( int y = 0; y < H; y++ ){
            for( int x = 0; x < W; x++ ){
                if( (x + y) % 2 ) continue;
                if( board[y][x] == 'X' ) continue;
                int bid = y * W + x + offset;
                for( int d = 0; d < 4; d++ ){
                    int wx = x + dx[d], wy = y + dy[d];
                    if( 0 <= wx && wx < W && 0 <= wy && wy < H && 
                        board[wy][wx] == '.' && wx % 2 == 0 ){
                        int wid = wy * W + wx;
                        mf.addEdge( bid, wid, 1 );
                    }
                }
            }
        }

        // 偶数の白マス -> T
        for( int y = 0; y < H; y++ ){
            for( int x = 0; x < W; x++ ){
                if( x % 2 || (x + y) % 2 == 0 ) continue;
                if( board[y][x] == 'X' ) continue;
                int id = y * W + x;
                mf.addEdge( id, T, 1 );
            }
        }

        return mf.get( S, T );
    }
};

// 以下 class MaxFlowの定義
MaxFlow::MaxFlow( int _max_n ){
    max_n = _max_n;
    G = new vector<Edge>[max_n];
    use = new bool[max_n];
}

MaxFlow::~MaxFlow(){
    delete[] G; G = 0;
    delete[] use; use = 0;
}

void MaxFlow::addEdge( int from, int to, int cap ){
    Edge e1 = { to, cap, G[to].size() };
    G[from].push_back(e1);
    Edge e2 = { from, 0, G[from].size()-1 };
    G[to].push_back(e2);
}

int MaxFlow::dfs( int v, int t, int cap ){
    if( v == t ) return cap;

    use[v] = true;
    int n = G[v].size();
    for( int i = 0; i < n; i++ ){
        Edge& e = G[v][i];
        if( e.cap == 0 || use[e.to] ) continue;
        int flow = dfs( e.to, t, min(cap, e.cap) );
        if( 0 < flow ){ 
            e.cap -= flow;
            G[e.to][e.rev].cap += flow;
            return flow;
        }
    }
    return 0;        
}

int MaxFlow::get( int s, int t ){
    int res = 0;
    while( true ){
        memset( use, false, sizeof(bool)*max_n );
        int add = dfs( s, t, INT_MAX );
        if( add == 0 ) break;
        res += add;
    }
    return res;
}

void MaxFlow::printGraph(){
    for( int i = 0; i < max_n; i++ ){
        printf( "%d - ", i );
        int n = G[i].size();
        for( int j = 0; j < n; j++ ){
            printf( "\tto=%d cp=%d rev=%d\n", G[i][j].to, G[i][j].cap, G[i][j].rev );
        }
        printf( "\n" );
    }
}