AOJ 2311: お菓子の魔女 / Dessert Witch

,

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2311

AOJ-ICPC 250はどれくらいなのだろうとやってみたが、はい。

solution

素直に実装するだけ。盤面の大きさ$n = 8$として$O(n^5)$。

implementation

#include <cstdio>
#include <array>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < int(n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
using namespace std;

constexpr int n = 8;
bool is_on_field(int y, int x) { return 0 <= y and y < n and 0 <= x and x < n; }
int main() {
    // input
    array<array<char, n>, n> f;
    repeat (y, n) repeat (x, n) scanf(" %c", &f[y][x]);
    // solve
    auto use = [](array<array<char, n>, n> f, int y, int x, char c) {
        int cnt = 0;
        repeat_from (dy, -1, +1+1) repeat_from (dx, -1, +1+1) if (dy != 0 or dx != 0) {
            f[y][x] = c;
            for (int k = 1; ; ++ k) {
                int ny = y + k*dy;
                int nx = x + k*dx;
                if (not is_on_field(ny, nx)) break;
                if (f[ny][nx] == '.') break;
                if (f[ny][nx] == c) {
                    while (-- k) {
                        f[y + k*dy][x + k*dx] = c;
                        ++ cnt;
                    }
                    break;
                }
            }
        }
        return make_pair(f, cnt);
    };
    int pass = 0;
    for (int turn = 0; ; ++ turn) {
        char c = turn % 2 == 0 ? 'o' : 'x';
        int result_y = -1, result_x = -1;
        int result = 0;
        repeat (y, n) repeat (x, n) if (f[y][x] == '.') {
            int cnt = use(f, y, x, c).second;
            if (result < cnt or (result == cnt and turn % 2 == 1)) {
                result_y = y;
                result_x = x;
                result = cnt;
            }
        }
        if (not result) {
            pass += 1;
            if (pass >= 2) {
                break;
            }
        } else {
            pass = 0;
            f = use(f, result_y, result_x, c).first;
        }
    }
    // output
    repeat (y, n) {
        repeat (x, n) {
            printf("%c", f[y][x]);
        }
        printf("\n");
    }
    return 0;
}