<7-4> DP - 킹 나이트 체스 (ChessMetric)

### DP ###

### TopCoder Collegiate Challenge 2003 Round 4 Div 1 Level 1 ###

 <소스코드>

- d[r][c][rest] : (r, c) 에서 (er, ec) 까지 rest 번만에 갈 수 있는 방법의 수

#include <vector>
#include <cstring>
using namespace std;
 
int n, er, ec;
int dr[] = {-1, -1, -1, 0, 0, 1, 1, 1, -2, -2, -1, 1, 2, 2, 1, -1};
int dc[] = {1, 0, -1, 1, -1, 1, 0, -1, 1, -1, -2, -2, -1, 1, 2, 2};
 
long long d[101][101][51];
 
bool safe(int r, int c)
{
    return (0 <= r && r < n) && (0 <= c && c < n);
}   
 
long long solve(int r, int c, int rest)
{
    long long *ret = &d[r][c][rest];
 
    if(rest == 0) {
        if(r == er && c == ec) return 1LL;
        return 0LL;
    }
    if(*ret != -1) return *ret;
 
    *ret = 0LL;
    for(int k=0; k<16; k++) {
        int nr = r+dr[k];
        int nc = c+dc[k];
        if(safe(nr, nc)) {
            *ret += solve(nr, nc, rest-1);
        }
    }
    return *ret;
}
 
class ChessMetric {
public:
    long long howMany(int size, vector<int> start, vector<int> end, int numMoves) {
        int sr = start[0];
        int sc = start[1];
        er = end[0]; ec = end[1];
        n = size;   
        
        memset(d, -1, sizeof(d));
        return solve(sr, sc, numMoves);
    }
};