LC 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

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Unique Paths III.

//

// Created by yuxi on 2019/1/21.

//

#include <vector>

#include <iostream>

using namespace std;

class Solution {

public:

  int cntzero;

  int ret;

  vector<vector<int>> dirs = {{,},{,-},{-,},{,}};

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

    vector<vector<int>> records(, vector<int>(,));

    ret = ;

    cntzero = ;

    for(int i=; i<grid.size(); i++) {

      for(int j=; j < grid[].size(); j++) {

        if(grid[i][j] == ) {

          records[][] = i;

          records[][] = j;

        } else if(grid[i][j] == ){

          records[][] = i;

          records[][] = j;

        } else if(grid[i][j] == ) cntzero++;

      }

    }

    int cnt = ;

    vector<bool> used(grid.size()*grid[].size(), false);

    vector<vector<int>> path;

    helper(grid, path, records[], records[], cnt, used);

    //cout << ret << endl;

    return ret;

  }

  void helper(vector<vector<int>>& grid, vector<vector<int>>& path, vector<int> s, vector<int>& e, int cnt, vector<bool>& used) {

//    for(int i=0; i<path.size(); i++) {

//      cout << "("<< path[i][0] << " " << path[i][1] << ")" << " ";

//    }

    //printgird(grid);

    int N = grid.size(), M = grid[].size();

    if(s[] == e[] && s[] == e[]) {

//      cout << "(" << s[0] << " " << s[1] << ")" << " " << endl;

      if(cnt == cntzero) ret++;

      return;

    }

    // cout << endl;

//    used[s[0]*N+s[1]] = true;

    grid[s[]][s[]] = -;

    path.push_back({s[],s[]});

    for(auto& dir : dirs) {

      int newx = dir[] + s[], newy = dir[] + s[];

      if(newx >=  && newx < N && newy >=  && newy < M && grid[newx][newy] != - && grid[newx][newy] !=  && grid[newx][newy] != -) {

        int newcnt = cnt;

        if(grid[newx][newy] == ) newcnt++;

        helper(grid, path, {newx, newy}, e, newcnt, used);

      }

    }

    grid[s[]][s[]] = ;

//    used[s[0]*N+s[1]] = false;

    path.pop_back();

  }

  void printgird(vector<vector<int>>& grid) {

    int N = grid.size(), M = grid[].size();

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

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

        cout << grid[i][j] << " ";

      }

      cout << endl;

    }

  }

};

巴特西

LC 980. Unique Paths III

最新文章

热门文章