980. Unique Paths III-白红宇的个人博客

980. Unique Paths III

发布日期：2021-05-09 02:50:42 浏览次数：20 分类：博客文章

本文共 4014 字，大约阅读时间需要 13 分钟。

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: 2Explanation: 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: 4Explanation: 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: 0Explanation: 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

My code:

class Solution {public:    int uniquePathsIII(vector
    
     
      >& grid) {        int ans;        pair
      
        start, end;        for (int i = 0; i < grid.size(); ++i) {            for (int j = 0; j < grid[0].size(); ++j) {                if (grid[i][j] == 1)                    start = {i, j};                if (grid[i][j] == 2)                    end = {i, j};            }        }                helper(grid, start, end);                return ans;    }    private:    int ans = 0;        void helper(const vector
       
        
         >& grid, const pair
         
          & start, const pair
          
           & end) { vector
           
            
             > temp = grid; int startX = start.first; int startY = start.second; // cout << start.first << " " << start.second << endl; // cout << end.first << " " << end.second << endl; dfs(temp, startX+1, startY, end); dfs(temp, startX-1, startY, end); dfs(temp, startX, startY+1, end); dfs(temp, startX, startY-1, end); } void dfs(vector
             
              
               > temp, int curX, int curY, const pair
               
                & end) { if (curX == end.first && curY == end.second && check(temp)) ans++, return; if (curX < 0 || curX >= temp.size() || curY < 0 || curY >= temp[0].size() || temp[curX][curY] != 0) return; // cout << curX << " " << curY << endl; temp[curX][curY] = 3; dfs(temp, curX+1, curY, end); dfs(temp, curX-1, curY, end); dfs(temp, curX, curY+1, end); dfs(temp, curX, curY-1, end); } bool check(vector
                
                 
                  >& temp) { for (int i = 0; i < temp.size(); ++i) { for (int j = 0; j < temp[0].size(); ++j) { if (temp[i][j] == 0) return false; } } return true; }};/*[[1,0,0,0], [0,0,0,0], [0,0,2,-1]]*/

��

Approach #2: DFS. [C++]

class Solution {public:    int uniquePathsIII(vector
    
     
      >& grid) {        int num = 1;        int sx = -1, sy = -1;        for (int i = 0; i < grid.size(); ++i)             for (int j = 0; j < grid[0].size(); ++j)                 if (grid[i][j] == 0) num++;                else if (grid[i][j] == 1) sx = i, sy = j;        return dfs(grid, sx, sy, num);    }    private:    int dfs(vector
      
       
        >& grid, int cx, int cy, int num) {        if (cx < 0 || cx >= grid.size() || cy < 0 || cy >= grid[0].size() || grid[cx][cy] == -1) return 0;        if (grid[cx][cy] == 2) return num == 0;        grid[cx][cy] = -1;        int path = dfs(grid, cx+1, cy, num-1)+                   dfs(grid, cx-1, cy, num-1)+                   dfs(grid, cx, cy+1, num-1)+                   dfs(grid, cx, cy-1, num-1);        grid[cx][cy] = 0;        return path;    }};

��

Analysis:

In the first code. I don't get the correct answer. Maybe my thinking is wrong in this problem.

上一篇：306. Additive Number

下一篇：784. Letter Case Permutation

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章