ソウルジェムゲーム (AOJ 2319)

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

問題

略

解法

片方の経路をfixし、もう一方の経路で最短路を見つける。validな経路はそこまで多くないので枝刈りをすれば間に合う。難しすぎるので詳しいことは略。

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

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))

struct Point {
  int state; // NG, OK
  int x;
  int y;
  int cost;
  Point() {;}
  Point(int state, int x, int y, int cost) : state(state), x(x), y(y), cost(cost) {;}
  bool operator<(const Point &rhs) const {
    return cost > rhs.cost;
  }
};

int h, w;
int rsx, rsy, rex, rey;
int bsx, bsy, bex, bey;
char field[20][20];

void PrintField() {
  REP(y, h) {
    REP(x, w) {
      printf("%c", field[y][x]);
    }
    puts("");
  }
}

bool visit[2][20][20];
int dist[2][20][20];
int calc() {
  const int dx[3] = { 1, 0, -1 };
  const int dy[3] = { 0, 1, 0, };
  priority_queue<Point> que;
  int initialState = 0;
  if (field[bsy][bsx] != 'K') { initialState = 1; }
  que.push(Point(initialState, bsx, bsy, 0));
  MEMSET(visit, 0);
  MEMSET(dist, 0x0f);
  while (!que.empty()) {
    Point p = que.top();
    que.pop();
    if (visit[p.state][p.y][p.x]) { continue; }
    visit[p.state][p.y][p.x] = true;
    if (p.state == 1 && p.x == bex && p.y == bey) {
      if (field[p.y][p.x] == 'K') { p.cost++; }
      return p.cost;
    }
    if (p.y == bey) { continue; }
    REP(dir, 3) {
      int nx = p.x + dx[dir];
      int ny = p.y + dy[dir];
      if (nx < 0 || nx >= w || ny < 0 || ny >= h) { continue; }
      if (nx == rsx && ny == rsy) { continue; }
      if (field[ny][nx] == '#') { continue; }
      int nstate = p.state;
      if (dir == 1 && field[ny][nx] != 'K') {
        nstate = 1;
      }
      int ncost = p.cost;
      if (field[p.y][p.x] == 'K' && field[ny][nx] == 'K') {;}
      else if (field[p.y][p.x] == 'K' || field[ny][nx] == 'K') { ncost += 2; }
      else if (field[p.y][p.x] == '.' && field[ny][nx] == '.') { ncost++; }

      if (visit[nstate][ny][nx] == '#') { continue; }
      if (dist[nstate][ny][nx] <= ncost) { continue; }
      dist[nstate][ny][nx] = ncost;
      que.push(Point(nstate, nx, ny, ncost));
    }
  }
  return 1 << 30;
}

int Init(int x, int y, int dir, int movey) {
  int ret = 1 << 30;
  if (x < 0 || x >= w || y < 0 || y >= h) { return 1 << 30; }
  if (field[y][x] != '.') { return 1 << 30; }
  if (movey != 1 && dir != -1) {
    for (int ny = y; ny >= 0; ny--) {
      if ((x == bsx && ny == bsy) ||
          (x == bex && ny == bey) ||
          field[ny][x] == '#') { break; }
      if (field[ny][x] == 'K') { return 1 << 30; }
    }
  }
  field[y][x] = 'K';
  if (x == rex && y == rey) {
    ret = calc();
  } else if (y == rey) {;}
  else {
    const int dx[2] = { 1, -1 };
    REP(i, 2) {
      int nx = x + dx[i];
      ret = min(ret, Init(nx, y, i, 0) + 1);
    }
    ret = min(ret, Init(x, y + 1, dir, 1) + 1);
  }
  field[y][x] = '.';
  return ret;
}

int main() {
  while (scanf("%d %d", &h, &w) > 0) {
    REP(y, h) {
      int v = scanf("%s", field[y]);
      assert(v == 1);
    }
    REP(y, h) REP(x, w) {
      if (field[y][x] == 'K') { rsx = x; rsy = y; field[y][x] = '.'; }
      if (field[y][x] == 'S') { bsx = x; bsy = y; field[y][x] = '.'; }
      if (field[y][x] == 'k') { rex = x; rey = y; field[y][x] = '.'; }
      if (field[y][x] == 's') { bex = x; bey = y; field[y][x] = '.'; }
    }
    int ans = 1 << 30;
    if (rsy >= rey || bsy >= bey) {}
    else {
      ans = min(ans, Init(rsx, rsy, -1, 1));
      swap(rsx, bsx);
      swap(rsy, bsy);
      swap(rex, bex);
      swap(rey, bey);
      ans = min(ans, Init(rsx, rsy, -1, 1));
    }
    if (ans >= (1 << 30)) puts("CONTRACT");
    else printf("%d\n", ans);
  }
}