TopCoder SRM611: ElephantDrinkingEasy

象が水を飲むときは、一番近いものを選ぶ。つまりそれぞれの象について、水を飲む場合はどこまで鼻を伸ばすかは一意に決まっている。

上側の象と下側の象が水を飲むかどうかは、\(2^{2n}\) 通り。上下の象が鼻を伸ばすかどうかが決まれば、左右の象がそれぞれ水を飲めるかどうかは一意に決まる。

よって上下の象が水を飲む飲まないパターンを全て試せばよい。\( O(n^2*2^{2n}) \)

public class ElephantDrinkingEasy {
    public int maxElephants(string[] map) {
        int n = map.Length;
        var topWater = new int[n];
        var bottomWater = new int[n];
        for (int i = 0; i < n; i++) {
            topWater[i] = bottomWater[i] = -1;
            for (int j = 0; j < n; j++) {
                if (map[j][i] == 'Y') {
                    if (topWater[i] == -1) topWater[i] = j;
                    bottomWater[i] = j;
                }
            }
        }
        int ans = 0;
        for (int topBit = 0; topBit < (1 << n); topBit++) {
            for (int bottomBit = 0; bottomBit < (1 << n); bottomBit++) {
                var existNose = new bool[n, n];
                int drinkableElephantNum = 0;
                for (int i = 0; i < n; i++) {
                    var topElephant = (topBit & (1 << i)) != 0;
                    var bottomElephant = (bottomBit & (1 << i)) != 0;
                    if (topElephant && topWater[i] != -1) {
                        drinkableElephantNum++;
                        for (int row = 0; row <= topWater[i]; row++) {
                            existNose[row, i] = true;
                        }
                    }
                    if (bottomElephant && bottomWater[i] != -1) {
                        if (topElephant && topWater[i] == bottomWater[i]) continue;
                        drinkableElephantNum++;
                        for (int row = bottomWater[i]; row < n; row++) {
                            existNose[row, i] = true;
                        }
                    }
                }
                for (int row = 0; row < n; row++) {
                    // left elephant
                    for (int col = 0; col < n; col++) {
                        if (existNose[row, col]) break;
                        existNose[row, col] = true;
                        if (map[row][col] == 'Y') {
                            drinkableElephantNum++;
                            break;
                        }
                    }
                    // right elephant
                    for (int col = n - 1; col >= 0; col--) {
                        if (existNose[row, col]) break;
                        existNose[row, col] = true;
                        if (map[row][col] == 'Y') {
                            drinkableElephantNum++;
                            break;
                        }
                    }
                }
                ans = Math.Max(ans, drinkableElephantNum);
            }
        }
        return ans;
    }
}