Проблема:
С учетом точных k шагов, сколько способов переместить точку из начальной точки в точку назначения? Точка может двигаться в восьми направлениях (по горизонтали, вертикали, по диагонали, против диагонали).
Я решил проблему через DP, но она работает только для прямоугольной доски, а не для прямоугольной доски. Я имею в виду, если dim[0]!=dim[1] в коде, это приведет к ошибке.
Здесь я могу предоставить контрольный пример:
Контрольный пример 1
dim = {5,6},start = {0,2},end = {2,2},steps = 4;
результат 50 (ожидаемый: 105)
Контрольный пример 2
dim = {5,5},int[] start = {0,2},end = {2,2},steps = 4;
результат равен 105 (ожидается: 105)
Вот код:
private static int[][] dir = {{0,1},{1,0},{1,1},{1,-1},{0,-1},{-1,0},{-1,-1},{-1,1}};
//DP
/*
@param dim, a tuple (width, height) of the dimensions of the board
@param start, a tuple (x, y) of the king's starting coordinate
@param target, a tuple (x, y) of the king's destination
*/
public static int countPaths2(int[] dim, int[] start, int[] des, int steps){
if(dim[0] == 0 || dim[1] == 0) return 0;
int[][][] dp = new int[dim[0]*dim[1]][dim[1]*dim[0]][steps+1];
for(int step = 0; step<=steps;step++){
for(int i = 0; i< dim[0]*dim[1];i++){
for(int j = 0; j< dim[0]*dim[1];j++){
if(step == 0 && i == j){
dp[i][j][step] = 1;
}
if(step >= 1){
for(int k =0; k< dir.length;k++){
int row = i / dim[0];
int col = i % dim[1];
if(row + dir[k][0] >= 0 && row + dir[k][0]< dim[0] && col + dir[k][1]>=0 && col + dir[k][1]< dim[1]){
int adj = (row + dir[k][0])*dim[0] + col + dir[k][1];
dp[i][j][step] += dp[adj][j][step-1];
}
}
}
}
}
}
int startPos = start[0]*dim[0] + start[1];
int targetPos = des[0]*dim[0] + des[1];
return dp[startPos][targetPos][steps];
}
public static void main(String[] args){
int[] dim = {5,5}; // can just use to square;
int[] start = {0,2};
int[] end = {2,2};
int steps = 7;
System.out.println(countPaths2(dim, start,end, steps));
}
Как я могу заставить его работать на любой доске?