方針
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]]; } }