# 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

``````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;
}
};
``````