Google Code Jam 2009 Round2 B （メモ）

書いてみた．
Haskellでは，面倒になることが予想されたので，C++で．
多分，標準的な解法だと思う．ただのDP.

#include <iostream>
#include <cstdlib>

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

const int R = 50, C = 50, U = R*C+1;
char cave[R][C];
int dig[R][C][C], emptyL[R][C], emptyR[R][C], groundL[R][C], groundR[R][C], depth[R][C];

inline void minimize(int r, int c, int d, int f, int cost)
{
  if (depth[r][c] <= f && dig[r][c][d] > cost) dig[r][c][d] = cost;
}

inline void build(int f, int r, int c, int d)
{
  int cost = dig[r][c][d];
  if ( cost == R*C+1 ) return;
  if ( cave[r+1][c] == '.')
	  minimize(r+1,c,c,f,cost);
  else
	{
	  int el = min(emptyL[r][d],emptyL[r][c]),er =  max(emptyR[r][d],emptyR[r][c]),
		gl = groundL[r][c], gr = groundR[r][c], left = max(el, gl), right = min(er, gr);
	  if (el < gl) minimize(r+1,gl-1,gl-1,f,cost);// fall down from left end
	  if (gr < er) minimize(r+1,gr+1,gr+1,f,cost);// fall down from right end
	  if (left == right) return; // dead end
	  minimize(r+1,left,left,f,cost + 1);// dig left end
	  minimize(r+1,right,right,f,cost + 1);// dig right end
	  for (int i = left+1; i < right; i++)
		for (int j = left; j <= right; j++)
		  minimize(r+1, i, j, f, cost + 1 + abs(i - j));
	}
}

int main()
{
  int cases;
  cin >> cases;
  for (int id = 1; id <= cases; id++)
	{
	  int r,c,f;
	  cin >> r >> c >> f;
	  // initialize
	  rep(i, R) rep(j, C) cave[i][j] = 0;
	  rep(i, r) rep(j, c) cin >> cave[i][j];
	  rep(i, r) rep(j, c)
		{ // pre-calculation
		  emptyL[i][j] = groundL[i][j] = j;
		  emptyR[i][c-j-1] = groundR[i][c-j-1] = c-j-1;
		  depth[r-i-1][j] = 1;
		  if (j > 0 && cave[i][j-1] == '.') emptyL[i][j] = emptyL[i][j-1];
		  if (j > 0 && i+1 < r && cave[i+1][j-1] == '#') groundL[i][j] = groundL[i][j-1];
		  if (c-j < C && cave[i][c-j] == '.') emptyR[i][c-j-1] = emptyR[i][c-j];
		  if (c-j < C && cave[i+1][c-j] == '#') groundR[i][c-j-1] = groundR[i][c-j];
		  if (r-i < R && cave[r-i][j] == '.') depth[r-i-1][j] += depth[r-i][j];
		}

	  rep(i, r) rep(j, c) rep(d, c) dig[i][j][d] = U; dig[0][0][0] = 0;
	  // building up DP table
	  rep(i, r-1) rep(j, c) rep(d, c) build(f,i,j,d);
	  // check answer
	  int cost = U;
	  rep(j, c) rep(d, c) if(cost > dig[r-1][j][d]) cost = dig[r-1][j][d];
	  cout << "Case #" << id << ": ";
	  if (cost < U) cout << "Yes " << cost << endl;
	  else cout << "No" << endl;
	}

}

# Haskell以外の言語だって使えるぞ．