ChessMetric TCCC '03 Round 4 easy

• DPの問題
• 格子状の道のある格子から別の格子に行くには何通り？という典型的な問題と同じタイプ。
  • 但し、動きが複雑なのでちょっと見通しにくくなっている。
  • また、格子状の道と違い、あるマスからあるマスまで行く時に、行き方によってステップ数が異なるので、「(x, y)に辿り着く行き方の組み合わせ数」だけでなく、「n歩で(x, y)に辿り着く行き方の組み合わせ数」を記録してあげる必要がある。
• DPは「昨日の計算結果が分かれば今日の計算結果が分かる」というアルゴリズムだけど、「昨日の結果」だけでなくて、「昨日までの結果全部」を取っとかないと行けない時もある。
  • 数学的帰納法も似たようなことがあった気がする。

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
class ChessMetric{
public:
  vector<vector<vector<long long> > > num; //[step][x][y]
  vector<int> dx, dy;
  int n;
  int sx, sy, ex, ey;

  void setup(){
    dx.resize(16);
    dy.resize(16);
    dx[0] = -1; dy[0] = 2;
    dx[1] = 1; dy[1] = 2;
    dx[2] = -2; dy[2] = 1;
    dx[3] = -1; dy[3] = 1;
    dx[4] = 0; dy[4] = 1;
    dx[5] = 1; dy[5] = 1;
    dx[6] = 2; dy[6] = 1;
    dx[7] = -1; dy[7] = 0;
    dx[8] = 1; dy[8] = 0;
    dx[9] = -2; dy[9] = -1;
    dx[10] = -1; dy[10] = -1;
    dx[11] = 0; dy[11] = -1;
    dx[12] = 1; dy[12] = -1;
    dx[13] = 2; dy[13] = -1;
    dx[14] = -1; dy[14] = -2;
    dx[15] = 1; dy[15] = -2;
  }

  long long howMany(int size, vector <int> start, vector <int> end, int numMoves){

    num.clear();
    num.resize(numMoves + 1, vector<vector<long long> >(size, vector<long long>(size, 0)));
    num[0][start[0]][start[1]] = 1;
    setup();

    for(int i = 1; i < numMoves + 1; i++){
      for(int x = 0; x < size; x++){
	for(int y = 0; y < size; y++){
	  for(int j = 0; j < 16; j++){
	    if(x + dx[j] >= 0 && x + dx[j] < size && y + dy[j] >= 0 && y + dy[j] < size){
	      num[i][x][y] += num[i - 1][x + dx[j]][y + dy[j]];
	    }
	  }
	}
      }
    }

    return num[numMoves][end[0]][end[1]];
  }


};