最短路径 DFS

Question

继续我的图论教育，我开始解决Maze II问题

迷宫中有一个球，其中有空位（表示为 0）并且 墙（表示为 1）。球可以通过空位 向上、向下、向左或向右滚动，但它不会停止滚动直到 撞墙。当球停止时，它可以选择下一个 方向

给定 m x n 迷宫、球的起始位置和目的地， 其中 start = [startrow, startcol] 和 destination = [destinationrow, destinationcol]，返回球停在的最短距离 目的地。如果球不能停在目的地，返回-1.

距离是球从 起始位置（不包括）到目的地（包括）。

为了弄湿我的脚，我编写了一个基于 DFS 的算法来检查每个单元格的每个方向，并在可能的情况下以深度优先的方式继续寻找“路径”，每次都记录步数。我有一个全局变量，用于检查当前计数是否较少，然后替换该值。但是，我的最短路径并不总是正确的。谁能解释我做错了什么？我知道 BFS 会产生最短路径，但我无法想象在不同方向完成的 BFS。

基本上，我只在撞墙时才改变方向，每次计数都会从递归函数开始的计数开始。例如，运行下面的算法应该产生 12 的最短路径，但我的算法吐出 16

public class MazeII {
    int shortest = Integer.MAX_VALUE;
    int[][] dirs = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    public static void main(String[] args) {
        int[][] maze = {{0,0,1,0,0},{0,0,0,0,0},{0,0,0,1,0},{1,1,0,1,1},{0,0,0,0,0}};
        int[] start = {0,4};
        int[] destination = {4,4};
        MazeII mii = new MazeII();
        System.out.println(mii.shortestDistance(maze, start, destination));
    }

    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        int count = 0;
        boolean[][] visited = new boolean[maze.length][maze[0].length];
        dfs(maze, start[0], start[1], destination, visited, count);
        return shortest == Integer.MAX_VALUE? -1 : shortest;
        
    }
    
    private void dfs(int[][] maze, int i, int j, int[] destination, boolean[][]visited, int count) {
        if( visited[i][j]) {
            return;
        }
        if (i == destination[0] && j == destination[1]) {
            shortest = Math.min(shortest, count);
            return;
        }
        
        visited[i][j] = true;

        for (int[] dir : dirs) {
            int x = i;
            int y  = j;
            int newcount = count;
            while (x + dir[0] >= 0 && x + dir[0] < maze.length &&
                    y + dir[1] >= 0 && y + dir[1] < maze[0].length &&
                    maze[x + dir[0]][y + dir[1]] == 0) {
                x+=dir[0];
                y+=dir[1];
                newcount++;
            }
            dfs(maze, x , y, destination, visited, newcount);
        }
    }

}