SRM 489 Div2 Hard SolitaireChess - Area1のif(memo[i][j])

問題

http://community.topcoder.com/stat?c=problem_statement&pm=11189

10x10チェスの盤面が2つ与えられる。コマはナイトとポーンの2種類がある。ポーンは最上段に移動するとナイトに変身できる。
盤面1から盤面2の状態にするためにコマを動かす回数の最小値を求めよ。不可能なら-1をかえせ。

やりかた

最小費用流。
ポーン♙はナイト♘へと変身できることから、盤面1から盤面2へのコマの移動、手順数は以下のように決められる。

・ポーン　→　ポーン
盤面1のポーンと盤面2のポーンが同じカラムにあり、かつ2のほうが上位にある場合のみ移動可能で手順数はマンハッタン距離。

・ナイト　→　ナイト
盤面1のポーンから盤面2のポーンへ移動する最小手順数をワーシャルフロイドでもとめる。

・ポーン　→　ナイト
まずポーンが最上段へ移動する手順とそこからナイトとして盤面2に移動する手順数の和。

・ナイト　→　ポーン
不可能。

これにしたがって盤面1の各コマから盤面2の各コマへとコストを手順数、容量を1として辺を張り、最小費用流を流せばOK。なお容量が1なのはあるコマが別のコマ1箇所へしか移動しないから。

以下ソース。

typedef pair<int, int> P;
const int MAX_V = 1000;
const int INF = 10000000;

struct edge{ int to, cap, cost, rev; };

int V;
vector<edge> G[MAX_V];
int h[MAX_V];
int dist[MAX_V];
int prevv[MAX_V], preve[MAX_V];

int min(int a, int b){
  return (a > b) ? b : a;
}

void add_edge(int from, int to, int cost, int cap){
  G[from].push_back((edge){to, cap, cost, (int)G[to].size()});
  G[to].push_back((edge){from, 0, -cost, (int)G[from].size() - 1});
}

int min_cost_flow(int s, int t, int f){
  int res = 0;
  fill(h, h + V, 0);
  while(f > 0){
    priority_queue<P, vector<P>, greater<P> > que;
    fill(dist, dist + V, INF);
    dist[s] = 0;
    que.push(P(0, s));
    while(!que.empty()){
      P p = que.top(); que.pop();
      int v = p.second;
      if(dist[v] < p.first) continue;
      for(int i = 0; i < (int)G[v].size(); i++){
        edge &e = G[v][i];
        if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]){
          dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
          prevv[e.to] = v;
          preve[e.to] = i;
          que.push(P(dist[e.to], e.to));
        }
      }
    }
    if(dist[t] == INF){
      return -1; // もうこれ以上流せない
    }
    for(int v = 0; v < V; v++) h[v] += dist[v];
    //s-t最短路にそって目一杯流す
    int d = f;
    for(int v = t; v != s; v = prevv[v]){
      d = min(d, G[prevv[v]][preve[v]].cap);
    }
    f -=d;
    res += d * h[t];
    for(int v = t; v != s; v = prevv[v]){
      edge &e = G[prevv[v]][preve[v]];
      e.cap -= d;
      G[v][e.rev].cap += d;
    }
  }
  return res;
}

int d[100][100];
int N, M;

bool inside(int y, int x){return 0 <= y && y < N && 0 <= x && x < M;}

class SolitaireChess {
public:

  int transform(vector <string> board1, vector <string> board2) {
    N = board1.size(); M = board1[0].length();

    //ナイトのポーンの数を数えて盤面1と2で食い違えば-1
    int nN1 = 0, nP1 = 0;
    int nN2 = 0, nP2 = 0;
    for(int i = 0; i < N; i++){
      for(int j = 0; j < M; j++){
	if(board1[i][j] == 'N') nN1++;
	if(board1[i][j] == 'P') nP1++;
	if(board2[i][j] == 'N') nN2++;
	if(board2[i][j] == 'P') nP2++;
      }
    }
    if(nN1 + nP1 != nN2 + nP2 || nP1 < nP2) return -1;

    //ナイトの盤面内移動について最小回数をwarshall-floydでもとめる
    int dy[8] = {2, 1, -1, -2, -2, -1, 1, 2};
    int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
    for(int i = 0; i < 100; i++) fill(d[i], d[i] + 100, INF);
    for(int i = 0; i < N; i++){ 
      for(int j = 0; j < M; j++){
	d[i * M + j][i * M + j] = 0;
	for(int k = 0; k < 8; k++)
	  if(inside(i + dy[k], j + dx[k])) d[i * M + j][(i + dy[k]) * M + j + dx[k]] = 1; 
      }
    }
    for(int k = 0; k < N * M; k++)
      for(int i = 0; i < N * M; i++) 
	for(int j = 0; j < N * M; j++)
	  d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    

    //盤面1の各コマから盤面2の各コマについて辺を張る
    V = 1000;
    for(int i = 0; i < V; i++) G[i].clear();
    int from = 0;
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < M; j++){
	if(board1[i][j] == '.') continue;
	int to = 200;
	for(int k = 0; k < N; k++){
	  for(int l = 0; l < M; l++){
	    if(board2[k][l] == '.') continue;
	    if(board1[i][j] == 'P' && board2[k][l] == 'P') add_edge(from, to, (j == l && k <= i) ? i - k : INF, 1);
	    else if(board1[i][j] == 'N' && board2[k][l] == 'N') add_edge(from, to, d[i * M + j][k * M + l], 1);
	    else if(board1[i][j] == 'N' && board2[k][l] == 'P') add_edge(from, to, INF, 1);
	    else if(board1[i][j] == 'P' && board2[k][l] == 'N') add_edge(from, to, d[j][k * M + l] + i, 1);
	    
	    to++;
	  }
	}
	from++;
      }
    }


    //始点から盤面1の各コマへ、盤面2の各コマから終点に辺を張る
    int s = 500, t = 501;
    int cnt1 = 0;
    for(int i = 0; i < N; i++)
      for(int j = 0; j < M; j++)
	if(board1[i][j] != '.') add_edge(s, cnt1++, 0, 1);
    
    int cnt2 = 200;
    for(int i = 0; i < N; i++)
      for(int j = 0; j < M; j++)
	if(board2[i][j] != '.') add_edge(cnt2++, t, 0, 1);

    int ans = min_cost_flow(s, t, cnt1);
    return ans >= INF ? -1 : ans;
  }
};