読者です 読者をやめる 読者になる 読者になる

日々精進

新しく学んだことを書き留めていきます

2003 TCCC Online Round 4 Easy

IT TopCoder

方針
DPで各マスに到達できる場合の数を数えていけばいいのですが、まだDPで解けばいいということに気付けません。。
ソースコード
私は盤面を再利用しましたが、三次元配列を使って履歴も保持した方がシンプルで不具合が出にくいかもしれませんね。

using System;
using System.Collections.Generic;
using System.Text;
 
 
 
 
public class ChessMetric
{
    public long howMany(int size, int[] start,
    int[] end, int numMoves)
    {
        long[] h = new long[16]{1,1,1,0,0,-1,-1,-1,2,2,1,1,-1,-1,-2,-2};
        long[] v = new long[16]{0,1,-1,1,-1,0,1,-1,1,-1,2,-2,2,-2,1,-1};
        long[,] dp = new long[size, size];
        dp[start[0], start[1]] = 1;
        for(long n = 0;n < numMoves;n++)
        {
            long[,] tempDp = new long[size, size];
            for (long i = 0; i < size; i++)
                for (long j = 0; j < size; j++)
                    for (long k = 0; k < 16; k++)
                        if (0 <= i + h[k] && i + h[k] < size && 0 <= j + v[k] && j + v[k] < size)
                            tempDp[i + h[k], j + v[k]] += dp[i, j];
            dp = tempDp;
        }
        return dp[end[0], end[1]];
    }
}