编程题:带障碍的机器人的最短路径

题目:输入为一个正数n以及一个block数组表示障碍所在的坐标x,y,机器人从左上角0,0开始,每一步只能走上下左右的位置,并且每走一步就会放block数组里面的一个障碍,如果机器人已经经过这个位置障碍就不放置,没有经过这个位置block就放置,直到block放置完成为止,如果机器人能够到达右下角就返回机器人所经过格子的最少个数,否则返回-1。

很明显,这道题就是要使用,bfs广度优先搜索,问题 就是在block数组如何限制下一步选择? 选用bfs带有step的函数模板,然后在每一个step,将status数组里面的block所在的位置设为无法到达,那么问题就解决了。

import java.util.ArrayList;
import java.util.LinkedList;

class Position{
    public int x;
    public int y;
    public Position(int x, int y){
        this.x = x;
        this.y = y;
    }
}
class Test9 {
    public int solution() {
        int n = 5;
        int [][] block = {{0,1}, {1,1}, {2,1}, {3,1}, {4,3}, {3,3}};
        int blockCount = block.length;
        int [][] status = new int[n][n];
        if (n == 1) return 1;

        LinkedList<Position> q = new LinkedList<Position>();
        int step = 0;
        int x = 0, y = 0;
        status[x][y] = 1;
        q.add(new Position(x, y));

        while (!q.isEmpty()) {
            int roundCount = q.size();
            for (int i = 0; i < roundCount; i++) {
                Position cur = q.poll();
                if (step < blockCount && status[block[step][0]][block[step][1]] == 0)
                    status[block[step][0]][block[step][1]] = 2;
                if(cur.x == n - 1 && cur.y == n - 1) return step + 1;
                for (Position p: getNextPosition(cur, status, n)){
                    status[p.x][p.y] = 1;
                    q.add(p);
                }
            }
            step ++;
        }
        return -1;
    }
    
    public ArrayList<Position> getNextPosition(Position cur, int[][] status, int n) {
        ArrayList<Position> al = new ArrayList<>();
        int x = cur.x, y = cur.y;
        if (x + 1 < n &&  status[x + 1][y] == 0) al.add(new Position(x + 1, y));
        if (y + 1 < n &&  status[x][y + 1] == 0) al.add(new Position(x, y + 1));
        if (x - 1 >= 0 &&  status[x - 1][y] == 0) al.add(new Position(x - 1, y));
        if (y - 1 >= 0 &&  status[x][y - 1] == 0) al.add(new Position(x, y - 1));
        return al;
    }

    public void printStatus(int [][] status) {
        for (int i = 0; i < status.length; i++) {
            for (int j = 0; j < status[0].length; j++) {
                System.out.print(status[i][j] + " ");
            }
            System.out.println();
        }
    }
}

下面为测试用例的调试结果,更加直观,1表示bfs访问到的节点,2表示每一个时间步放置的障碍。

发表评论

电子邮件地址不会被公开。 必填项已用*标注