优化KnightL棋盘问题递归解法的时间复杂度

问题描述 #

给定n×n棋盘，需计算每个1≤a,b<n的KnightL(a,b)从(0,0)到(n-1,n-1)的最少移动步数，不可达则返回-1。当前递归实现的代码在n≤5时可正常运行，但n≥6时时间复杂度极高，需优化。

原递归代码 #

public class lknightmycode {

    public static boolean canreach(int[][] board, int row, int col) {
        if(row >= 0 && col >= 0 && row < board.length && col < board.length && board[row][col] == -1){
            return true;
        } else {
            return false;
        }
    }

    public static int helper(int[][] board, int row, int col, int crow, int ccol, int steps) {
        if (crow == board.length - 1 && ccol == board.length - 1){
            return steps;
        }
        if (canreach(board, crow, ccol)) {
            board[crow][ccol] = 0;
            
            int minSteps = Integer.MAX_VALUE;
            int[] dr = {-row, -row, row, row, col, -col, col, -col};
            int[] dc = {col, -col, col, -col, -row, -row, row, row};

            for (int i = 0; i < 8; i++) {
                int newRow = crow + dr[i];
                int newCol = ccol + dc[i];

                int currentSteps = helper(board, row, col, newRow, newCol, steps + 1);
                if (currentSteps != -1) {
                    minSteps = Math.min(minSteps, currentSteps);
                }
            }
            board[crow][ccol] = -1; // Reset the board position

            return (minSteps == Integer.MAX_VALUE) ? -1 : minSteps;
        }
        
        return -1;
    }

    public static int[][] knightlOnAChessboard(int n) {
        int[][] board = new int[n][n];
        int[][] Result = new int[n - 1][n - 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = -1;
            }
        }
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j <= i; j++) {
                Result[i][j] = helper(board, i + 1, j + 1, 0, 0, 0);
                Result[j][i] = Result[i][j];
                board = new int[n][n];
                for (int x = 0; x < n; x++) {
                    for (int y = 0; y < n; y++) {
                        board[x][y] = -1;
                    }
                }
            }
        }
        return Result;
    }

    public static void main(String[] args) {
        int n = 5;
        int[][] result = knightlOnAChessboard(n);
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < n-1; j++) {
                System.out.print(result[i][j] + " ");
            }
            System.out.println();
        }
    }
}

优化方案 #

核心优化：用BFS替代递归DFS #

递归DFS会深度遍历所有可能路径，存在大量重复计算，导致n≥6时超时。而BFS是层级遍历，首次到达目标点的步数即为最短路径，时间复杂度为O(n²)，远优于DFS。

其他优化点 #

• 复用距离数组：针对每个(a,b)，创建距离数组记录每个格子的最短步数，初始为-1，起点(0,0)设为0，避免重复访问。
• 利用对称性：KnightL(a,b)和KnightL(b,a)的移动规则对称，计算一次结果即可填充两个位置，减少一半计算量。
• 预定义移动方向：提前生成8个方向的偏移量，避免每次循环重复创建数组。

优化后的代码 #

import java.util.LinkedList;
import java.util.Queue;

public class KnightLOptimized {

    private static int bfs(int n, int a, int b) {
        int[][] dist = new int[n][n];
        // 初始化距离数组为-1，表示未访问
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = -1;
            }
        }
        Queue<int[]> queue = new LinkedList<>();
        dist[0][0] = 0;
        queue.add(new int[]{0, 0});

        // 8个移动方向
        int[] dr = {-a, -a, a, a, -b, -b, b, b};
        int[] dc = {-b, b, -b, b, -a, a, -a, a};

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int row = curr[0];
            int col = curr[1];

            // 到达终点，返回步数
            if (row == n-1 && col == n-1) {
                return dist[row][col];
            }

            for (int i = 0; i < 8; i++) {
                int newRow = row + dr[i];
                int newCol = col + dc[i];
                // 检查是否在棋盘内且未访问
                if (newRow >= 0 && newRow < n && newCol >=0 && newCol < n && dist[newRow][newCol] == -1) {
                    dist[newRow][newCol] = dist[row][col] + 1;
                    queue.add(new int[]{newRow, newCol});
                }
            }
        }
        // 无法到达终点
        return -1;
    }

    public static int[][] knightlOnAChessboard(int n) {
        int[][] result = new int[n-1][n-1];
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j <= i; j++) {
                int steps = bfs(n, i+1, j+1);
                result[i][j] = steps;
                result[j][i] = steps;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int n = 6;
        int[][] res = knightlOnAChessboard(n);
        for (int[] row : res) {
            for (int num : row) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }
}

内容的提问来源于stack exchange，提问作者Aatmik Mittal