1
// 980. Unique Paths III
2
var uniquePathsIII = function (grid) {
3
  const M = grid.length; // grid height
4
  const N = grid[0].length; // grid width
5
  let result = 0; // final result
6
  let startY = 0,
7
    startX = 0; // starting point coordinates
8
  let finalY = 0,
9
    finalX = 0; // endpoint coordinates
10
  let empty = 0; // count of empty squares
11
  let visit = Array(M); // visited squares (MxN of booleans)
12

13
  // Initialization of required variables
14
  for (let i = 0; i < M; i++) {
15
    visit[i] = Array(N).fill(false); // now: "visit[i][j] === false"
16
    for (let j = 0; j < N; j++) {
17
      switch (grid[i][j]) {
18
        case 0:
19
          empty++;
20
          break;
21
        case 1:
22
          startY = i;
23
          startX = j;
24
          break;
25
        case 2:
26
          finalY = i;
27
          finalX = j;
28
          break;
29
      }
30
    }
31
  }
32

33
  // Recursively run DFS and get the answer in the "result" variable
34
  dfs(startY, startX, visit, 0);
35
  return result;
36

37
  // DFS implementation
38
  function dfs(startY, startX, visit, step) {
39
    // If it's a wrong square, then exit immediately
40
    if (
41
      startY < 0 ||
42
      startY >= M || // off grid (height)
43
      startX < 0 ||
44
      startX >= N || // off grid (width)
45
      visit[startY][startX] || // already processed
46
      grid[startY][startX] === -1 // this is an obstacle
47
    )
48
      return; // ... exit now
49

50
    // Base case: we're at the endpoint, need to stop the recursion.
51
    // If all of squares are visited, increase the "result":
52
    // (count of paths from start to the end).
53
    if (startY === finalY && startX === finalX) {
54
      if (step - 1 === empty) result++;
55
      return;
56
    }
57

58
    // Run DFS for neighboring squares.
59
    // Increase the number of steps (count of the visited squares).
60
    visit[startY][startX] = true; // mark current square as visited
61
    dfs(startY - 1, startX, visit, step + 1); // top
62
    dfs(startY, startX + 1, visit, step + 1); // right
63
    dfs(startY + 1, startX, visit, step + 1); // bottom
64
    dfs(startY, startX - 1, visit, step + 1); // left
65
    visit[startY][startX] = false; // restore visited square
66
  }
67
};