お菓子の魔女 (AOJ 2311)

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

問題

略

解法

やるだけ。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

int h = 8;
int w = 8;
int field[10][10];
int tempField[10][10];
int dx[8] = { 1, 1, 1, 0, -1, -1, -1, 0 };
int dy[8] = { -1, 0, 1, 1, 1, 0, -1, -1 };

void PrintField(int field[10][10]) {
  REP(y, h) {
    REP(x, w) {
      int c = field[y][x];
      if (c == -1) { putchar('.'); }
      if (c == 0) { putchar('o'); }
      if (c == 1) { putchar('x'); }
    }
    puts("");
  }
}

int Put(int sx, int sy, int player) {
  int ret = 0;
  if (field[sy][sx] != -1) { return 0; }
  memcpy(tempField, field, sizeof(field));
  tempField[sy][sx] = player;
  REP(dir, 8) {
    int lcnt = 0;
    int nx = sx;
    int ny = sy;
    while (true) {
      nx += dx[dir];
      ny += dy[dir];
      if (nx < 0 || nx >= w || ny < 0 || ny >= h || tempField[ny][nx] == -1) {
        lcnt = 0;
        break;
      }
      if (tempField[ny][nx] == player) { break; }
      lcnt++;
    }
    if (lcnt == 0) { continue; }
    nx = sx;
    ny = sy;
    while (true) {
      nx += dx[dir];
      ny += dy[dir];
      if (tempField[ny][nx] == player) { break; }
      tempField[ny][nx] ^= 1;
    }
    ret += lcnt;
  }
  return ret;
}

void calc(int player, int pass) {
  if (pass == 2) { return; }
  //PrintField(field);
  //puts("");
  int cnt = 0;
  int ansy = -1;
  int ansx = -1;
  int sy = player == 0 ? 0 : h - 1;
  int sx = player == 0 ? 0 : w - 1;
  int dir = player == 0 ? 1: -1;
  for (int y = sy; 0 <= y && y < h; y += dir) {
    for (int x = sx; 0 <= x && x < w; x += dir) {
      int lcnt = Put(x, y, player);
      if (lcnt > cnt) {
        cnt = lcnt;
        ansx = x;
        ansy = y;
      }
    }
  }
  if (cnt == 0) {
    calc(player ^ 1, pass + 1);
  } else {
    Put(ansx, ansy, player);
    memcpy(field, tempField, sizeof(field));
    calc(player ^ 1, 0);
  }
}

int main() {
  while (true) {
    MEMSET(field, -1);
    REP(y, h) {
      REP(x, w) {
        char c;
        int v = scanf(" %c ", &c);
        if (v != 1) { return 0; }
        if (c == 'o') { field[y][x] = 0; }
        if (c == 'x') { field[y][x] = 1; }
      }
    }
    calc(0, 0);
    PrintField(field);
  }
}