Robot in a Grid

作者 QIFAN 日期 2016-10-01
Robot in a Grid

Imagine a robot sitting on the upper left corner of grid with r rows and c columns. The robot can only move in two directions, right and down, but certain cells are “off limits” such that the robot cannot step on them. Design an algorithm to find a path for the robot from the top left to the bottom right.

思路

假设矩阵为二位布尔数组maze,若maze[i][j]==true则可以走,反之则表示不能走。

假设机器人在(i, j)(第i行第j列),则它的上一步必然在(i-1, j)(i, j-1)

terminal case 返回false

  • 超出界限。i < 0 || i >= n || j < 0 || j >= n
  • 不能走。maze[i][j]==false
  • 若出发点为(0,0),则该路径可行,返回true

解题

  • recursive
    public ArrayList<Point> getPath(boolean[][] maze) {
    if (maze == null || maze.length == 0 || maze[0].length == 0) return new ArrayList<Point>;
    ArrayList<Point> path = new ArrayList<>();
    int[][] pathmap = new int[maze.length][maze[0].length];
    Arrays.fill(pathmap, -1);
    if(getPath(maze, maze.length - 1, maze[0].length - 1, path, pathmap)) {
    return path;
    }
    return new ArrayList;
    }
    public int getPath(boolean[][] maze, int row, int col, ArrayList<Point> path, int[][] pathmap) {
    if (row < 0 || col < 0 || !maze[row][col]) return;
    if(pathmap[row][col] != -1) return path[row][col];
    if((row == 0 && col == 0) || getPath(maze, row - 1, col, path, pathmap) || getPath(maze, row, col - 1, path, pathmap)) {
    pathmap[row][col] = 1;
    path.add(new Point(row, col));
    return 1;
    }
    pathmap[row][col] = 0;
    return 0;
    }

分析

假设共有r行,c列
时间复杂度O(rc)
空间复杂度O(rc)