AOJ 2311: お菓子の魔女 / Dessert Witch
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;
}