leetcode 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.

Example 1:

Input: [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]

Output: 2

Explanation: We have the following two paths:

1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)

2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

Example 2:

Input: [[1,0,0,0],[0,0,0,0],[0,0,0,2]]

Output: 4

Explanation: We have the following four paths:

1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)

2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)

3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)

4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)

Example 3:

Input: [[0,1],[2,0]]

Output: 0

Explanation:

There is no path that walks over every empty square exactly once.

Note that the starting and ending square can be anywhere in the grid.

Note:

1 <= grid.length * grid[0].length <= 20

思路：深搜，终止条件到达目标位置，以及可到达的位置全部走了一遍，算一条路径。

 class Solution {

     int dx[] = {, -, , };

     int dy[] = {, , -, };

 public:

     int uniquePathsIII(vector<vector<int>>& grid) {

         int m = grid.size();

         if (m == )

             return ;

         int n = grid[].size();

         int todo = ;

         int start_x, start_y, end_x, end_y;

         for (int i = ; i < m; i++) {

             for (int j = ; j < n; j++) {

                 if (grid[i][j] != -) { //记录要走的总的位置数

                     todo++;

                     if (grid[i][j] == ) { //记录起始位置

                         start_x = i;

                         start_y = j;

                     } else if (grid[i][j] == ) { //记录终点

                         end_x = i;

                         end_y = j;

                     }

                 }

             }

         }

         int ans = ;

         dfs(grid, start_x, start_y, end_x, end_y, todo, ans, m, n);

         return ans;

     }

     void dfs(vector<vector<int> > &grid, int sx, int sy, const int ex, const int ey, int todo, int &ans, int row, int col) {

         todo--;

         if (todo < )

             return ;

         if (sx == ex && sy == ey) {

             if (todo == ) ans++;

             return;

         }

         //上下左右四个方向

         for (int k = ; k < ; k++) {

             int new_x = sx + dx[k];

             int new_y = sy + dy[k];

             if (new_x >=  && new_x < row && new_y >=  && new_y < col) {

                 if (grid[new_x][new_y] ==  || grid[new_x][new_y] == ) {

                     grid[new_x][new_y] = -;

                     dfs(grid, new_x, new_y, ex, ey, todo, ans, row, col);

                     grid[new_x][new_y] = ;

                 }

             }

         }

     }

 };

巴特西

leetcode 980. Unique Paths III

最新文章

热门文章