搜索（BFS）---计算在网格中从原点到特定点的最短路径长度

计算在网格中从原点到特定点的最短路径长度

[[1,1,0,1],

 [1,0,1,0],

 [1,1,1,1],

 [1,0,1,1]]

题目描述：

1表示可以经过某个地方，求解从（0，0）位置到（tr，tc）位置的最短路径长度。

思路分析：

使用BFS思想从（0，0）点开始搜索，直到找到（tr,tc）。

代码：

public int minPathLength(int[][]grids,int tr,int tc){

    int[][]direction={{1,0},{-1,0},{0,1},{0,-1}} //表示四个方向

    int m=grids.length;

    int n=grids[0].length;

    int pathLength=0;

    if(m==0||tr<0||tc<0)

        return -1;

    Queue<Pair<Integer,Integer>>queue=new LinkedList<>();//队列中存放每次访问到的点的坐标

    queue.offer(new Pair<Integer,Integer>(0,0));

    while(!queue.isEmpty()){

        int size=queue.size(); //队列中是否有元素

        pathLength++; //每循环一次，长度加一

        while(size-->0){

            Pair<Integer,Integer>cur=queue.poll();

            int cr=cur.getKey(); //当前点的行坐标

            int cc=cur.getValue(); //当前点的列坐标

            grids[cr][cc]=0; //标记当前点已经访问过

            for(int[]d:direction){

                int nr=cr+d[0];

                int nc=cc+d[1]; //下一个点的横纵坐标

                if(nr<0||nr>=m||nc<0||nc>=n||grids[nr][nc]==0){

                    continue;

                }

                if(nr==tr&&nc==tc){

                    return pathLength;

                }

                queue.offer(new Pair<>(nr,nc));

            }

        }

    }

    return -1;

}

巴特西

搜索（BFS）---计算在网格中从原点到特定点的最短路径长度

计算在网格中从原点到特定点的最短路径长度

题目描述：

思路分析：

代码：

最新文章

热门文章