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