TopCoder SRM580: WallGameDiv2

壁は水平に並べるだけでよい。そうすると「ウサギ」は「左右にいくつか移動して、下に一歩移動する」のアクションを繰り返すように強制できる。

あとは、「ウナギの現在位置」を状態にして動的計画法を使えば良い。

public class WallGameDiv2 {
    static public bool Between(long a, long x, long b) { return a <= x && x < b; }
    static public void UpdateMax<T>(ref T x, T newValue) where T : IComparable<T> { if (x.CompareTo(newValue) < 0) x = newValue; }

    const long inf = 1 << 30;

    public long ToLong(char c) {
        if (c == 'x') return -inf;
        return c - '0';
    }

    public int play(string[] _costs) {
        var costs = _costs.Select(s => s.Select(ToLong).ToArray()).ToArray();
        int w = costs[0].Length;
        int h = costs.Length;
        var dp = Enumerable.Range(0, h).Select(_ => Enumerable.Repeat(-inf, w).ToArray()).ToArray();
        dp[0][0] = 0;
        for (int row = 0; row < h - 1; row++) {
            for (int col = 0; col < w; col++) {
                for (int moveTo = 0; moveTo < w; moveTo++) {
                    var targetCell = costs[row + 1][moveTo];
                    var path = costs[row].Where((c, index) => Between(col + 1, index, moveTo + 1) || Between(moveTo, index, col));
                    var cost = path.DefaultIfEmpty(0).Sum() + targetCell;
                    UpdateMax(ref dp[row + 1][moveTo], dp[row][col] + cost);
                }
            }
        }

        return (int)dp.Last().Max();
    }
}