SRM 530 div1 easy: GogoXCake

問題

TopCoder Statistics - Problem Statement

解法

切り取られていなければならない部分を左上から探索します。

class GogoXCake {
public:
    string solve(vector <string> cake, vector <string> cutter) {
        int H = cake.size(), W = cake[0].size();
        int n = cutter.size(), m = cutter[0].size();
        int first = 0;
        for (; ; first++) if (cutter[0][first] == '.') break;
        for (int h = 0; h < H; h++) for (int w = 0; w < W; w++) {
            if (cake[h][w] == '.') {
                if (w < first) return "NO";
                if (w+m-first > W) return "NO";
                if (h+n > H) return "NO";
                for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
                    int y = h+i, x = w+j-first;
                    if (cutter[i][j] == '.') {
                        if (cake[y][x] == 'X') return "NO";
                        cake[y][x] = 'X';
                    }
                }
            }
        }
        for (int h = 0; h < H; h++) for (int w = 0; w < W; w++) if (cake[h][w] == '.') return "NO";
        return "YES";
    }
};