Unique Paths III

Question

http://www.lintcode.com/en/problem/unique-paths-iii/
Follow up for "Unique Paths II": https://acm.errong.win/uniquepathsii/
Now each grid contains a value, so each path also has a value. Find the sum of all the unique values paths.

Example

For example,
[
[1,1,2],
[1,2,3],
[3,2,4]
]
There are 2 unique value path:
[1,1,2,3,4] = 11
[1,1,2,2,4] = 10
return 21

Answer

class Solution {
public:
 /*
 * @param : an array of arrays
 * @return: the sum of all unique weighted paths
 */
 int uniqueWeightedPaths(vector<vector<int>> &obstacleGrid) {
  int m = obstacleGrid.size();
  if (m <= 0)
   return 0;
  int n = obstacleGrid[0].size();
  if (n <= 0)
   return 0;
  struct Up {
   int step;
   int sum;
   Up(int st, int su) : step(st), sum(su) {}
  };
  map<int, vector<Up>> sum_paths;
  sum_paths[0] = vector<Up>();
  sum_paths[0].push_back(Up(0, obstacleGrid[0][0]));
  for (int i = 1; i < m + n - 1; i++) {
   map<int, vector<Up>> new_sum_paths;
   for (auto sp : sum_paths) {
    int pos = sp.first;
    int x = pos / n;
    int y = pos % n;
    int nx = x + 1;
    int ny = y;    
    if (nx < m) {
     int npos = nx * n + ny;
     for (auto up : sp.second) {
      if (up.step < i) {
       Up nup = up;
       nup.sum += obstacleGrid[nx][ny];
       nup.step += 1;
       bool found = false;
       if (!new_sum_paths.count(npos)) {
        new_sum_paths[npos] = vector<Up>();
       }
       for (auto eup : new_sum_paths[npos]) {
        if (eup.sum == nup.sum) {
         found = true;
         break;
        }
       }
       if (!found)
        new_sum_paths[npos].push_back(nup);
      }
     }
    }
    nx = x;
    ny = y + 1;
    if (ny < n) {
     int npos = nx * n + ny;
     for (auto up : sp.second) {
      if (up.step < i) {
       Up nup = up;
       nup.sum += obstacleGrid[nx][ny];
       nup.step += 1;
       bool found = false;
       if (!new_sum_paths.count(npos)) {
        new_sum_paths[npos] = vector<Up>();
       }
       for (auto eup : new_sum_paths[npos]) {
        if (eup.sum == nup.sum) {
         found = true;
         break;
        }
       }
       if (!found)
        new_sum_paths[npos].push_back(nup);
      }
     }
    }
   }
   sum_paths = new_sum_paths;
  }
   int sum = 0;
  int pos = m*n - 1;
  for (auto sp : sum_paths[pos]) {
   sum += sp.sum;
  }
  return sum;
 }
};

❤️ Support This Blog

---

If this post helped you, you can support my writing with a small donation. Thank you for reading.

---

Coffee ☕ Thanks 🙏 Extra Support ❤️