java - 为什么动态规划解法只适用于方板？

Question

问题是:

Given exact k steps, how many ways to move a point from start point to destination? Point can move for eight directions(horizontally, vertically, diagonally, anti-diagonally).

我通过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));

}

我怎样才能让它适用于任何类型的主板？

Answer 1

罪魁祸首是:

int row = i / dim[0];
int col = i % dim[1]; // <- this should have been dim[0]

在 div/mod 模式中，您应该除以相同的数字并取模...