WARush

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

SRM611 Div2 Hard "ElephantDrinkingEasy"

問題

TopCoder Statistics - Problem Statement

N * Nのグリッド状のマスで構成されたフィールドがある。いくつかのマスは水場となっている。あなたはフィールドの状態を表したString[] fieldが与えられる。field[i][j]が'Y'であれば、マス(i, j)は水場であり、'N'であればそうでないことを表す。

下図の緑色の部分が表すように、フィールドを囲うようにして4 * Nの象がいる。1つのマスには一頭の象がいる。象は鼻で水を飲むことができる。それぞれの象はフィールドに対し、まっすぐ伸ばした鼻のみ入ることができる。なので、フィールドの左側にいる象は鼻を右に伸ばすことになる。鼻は、フィールドの端から端まで伸ばすことができる。
f:id:Ekaing:20140309234240p:plain

さらに制限があり、象の鼻が交差することはできない。それぞれの水場は、一頭の象しか利用できない。

例えば、図の(a)は制限を満たしている。水場は青、象は緑、象の鼻は赤である。ここでは4頭の象が水を飲んでいる。図の(b), (c)は制限を満たしていない。両方とも鼻が交差してしまっている。

課題は、同時に水を飲むことができる像の数の最大値を求めることである。

制約

2 <= N <= 5


考えたこと

像の数は最大でも5 * 4の20頭。それぞれの象が飲む・飲まないの状態があるが、2^20 = 3000万ぐらいなので、シミュレートでいける。

実装方法として、N頭ごとにフィールドを90度回転させてやると楽かもしれない。


ソースコード

int N;

class ElephantDrinkingEasy {
public:

    // 90度回転させる
    vector <string> rotate(vector <string> M) {
        vector<string> res;

        for (int y = 0; y < N; y++) {
            res.push_back("");
            for (int x = 0; x < N; x++) {
                int sy = N - 1 - x;
                int sx = y;
                res[y] += M[sy][sx];
            }
        }

        return res;
    }
    
    int dfs(int i, vector <string> M) {

        if (i == N * 4) {
            return 0;
        }

        // N頭ごとにフィールドを90度回転
        if (i % N == 0) {
            M = rotate(M);
        }

        // 吸わない
        int res = dfs(i + 1, M);

        // 吸う
        int x = i % N;
        for (int y = 0; y < N; y++) {
            // 水を見つけた
            if (M[y][x] == 'Y') {
                for (int yy = 0; yy <= y; yy++) M[yy][x] = 'X';
                res = max(res, dfs(i + 1, M) + 1);
            }
            if (M[y][x] == 'X') break;
        }

        return res;
    }


    int maxElephants(vector <string> map) {
        N = map.size();
        
        return dfs(0, map);
    }
};