[LeetCode] Unique Paths III

980. Unique Paths III

On a 2-dimensional grid, there are 4 types of squares:

  • 1 represents the starting square. There is exactly one starting square.
  • 2 represents the ending square. There is exactly one ending square.
  • 0 represents empty squares we can walk over.
  • -1 represents obstacles that we cannot walk over.

Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.

  • new solution update 2022.02.15
  • Time : O(n)
  • Space : O(1)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution {
    public:
    int uniquePathsWithObstacles(vector<vector<int>>& ob) {
    int n = ob.size(), m = ob[0].size();
    if(ob[0][0] == 1 or ob[n-1][m-1] == 1) return 0;
    for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++)
    if(ob[i][j] == 1) ob[i][j] = -1;
    }
    for(int i = 0; i < m and ob[0][i] == 0; i++) ob[0][i] = 1;
    for(int i = 1; i < n and ob[i][0] == 0; i++) ob[i][0] = 1;

    for(int i = 1; i < n; i++) {
    for(int j = 1; j < m; j++) {
    if(ob[i][j] == -1) continue;
    ob[i][j] = (ob[i-1][j] == -1 ? 0 : ob[i-1][j]) + (ob[i][j-1] == -1 ? 0 : ob[i][j-1]);
    }
    }
    return ob[n-1][m-1];
    }
    };
  • Time : O(n)
  • Space : O(n)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    class Solution {
    pair<int, int> start, end;
    int route = 2, n, m;
    vector<vector<bool>> v;
    int dx[4]{0,1,0,-1}, dy[4]{-1,0,1,0};
    int dfs(int y, int x, int path) {
    if(y == end.first && x == end.second) return path == route;
    v[y][x] = true;
    int res(0);
    for(int i = 0; i < 4; i++) {
    int ny(y + dy[i]), nx(x + dx[i]);
    if(0 <= ny && ny < n && 0 <= nx && nx < m && !v[ny][nx]) {
    res += dfs(ny, nx, path + 1);
    }
    }
    v[y][x] = false;
    return res;
    }
    public:
    int uniquePathsIII(vector<vector<int>>& grid) {
    n = grid.size(), m = grid[0].size(), v = vector<vector<bool>>(n, vector<bool>(m, false));
    for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {
    if(grid[i][j] == 1) start = {i, j};
    else if(grid[i][j] == 2) end = {i, j};
    else if(!grid[i][j]) route++;
    else v[i][j] = true;
    }
    }

    return dfs(start.first, start.second, 1);
    }
    };
Author: Song Hayoung
Link: https://songhayoung.github.io/2021/06/26/PS/LeetCode/unique-paths-iii/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.