書いてみた．

Haskellでは，面倒になることが予想されたので，C++で．

多分，標準的な解法だと思う．ただのDP. 

#include <iostream>
#include <cstdlib>
using namespace std;
#define rep(i, n) for (int i = ; 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] <= f && dig[r][d] > cost) dig[r][d] = cost;
}
inline void build(int f, int r, int c, int d)
{
int cost = dig[r][d];
if ( cost == R*C+1 ) return;
if ( cave[r+1] == '.')
minimize(r+1,c,c,f,cost);
else
{
int el = min(emptyL[r][d],emptyL[r]),er =  max(emptyR[r][d],emptyR[r]),
gl = groundL[r], gr = groundR[r], 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] = ;
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 >  && cave[i][j-1] == '.') emptyL[i][j] = emptyL[i][j-1];
if (j >  && 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[][][] = ;
// 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以外の言語だって使えるぞ．