knight_moves.cpp

来自「骑士从棋盘左下角出发到右下角的走法有多少种？本程序用动态规划的方法实现」· C++ 代码 · 共 46 行

/*
 Author: BlueBlood--六院一队吴诚堃是也，其学号：200306020093
 Explantion: Perhaps many people like to use recursion mathod, but as I have been practise using Dynamic Programming, 
 						I did it in my own DP way, which is efficient when the dimensions are larger.
 						Again, this problem is similiar to the problem "Pascal' Travel" on Peking University Online Judge. ^-^
 						Everyone no matter his age or sex, he can do DP.
 */
#include <stdio.h>

int board[9][5];
int total;
int dir[4][2] = {{1,-2},{2, -1},{2,1},{1,2}};
int i,j;

int main()
{
	for (i = 0; i < 9; i++)
		for (j = 0; j < 5; j++)
			board[i][j] = 0;
	
	board[0][0] = board[1][2] = board[2][1] = 1;
	
	for (i = 1; i < 9; i++)
		for (j = 0; j < 5; j++)
		{
			if ( board[i][j] != 0 )
			{
				for (int k = 0; k < 4; k++)
				{
					int x = i + dir[k][0];
					int y = j + dir[k][1];
					
					if ( x < 0 || x >= 9 || y < 0 || y >= 5 )
						continue;
					
					board[x][y] += board[i][j];
				}
			}
		}
		
		
	printf("%d\n", board[8][4]);
	
	return 0;
}