[LeetCode]Swim in Rising Water

图的连接性的问题，第一个想法就是Union Find，Union Find的具体讲解可以参考这篇文章。因为高度的范围是[0, n^2 - 1]，我们只需要先遍历所有edge，因为有的edge是到特定的高度才会出现，所以我们建立高度到edges的映射。从0到n^2 - 1遍历所有高度，每次加入对应的edges，知道发现起点和终点连通了，我们就找到了满足条件的最小高度。时间复杂度O(n^2 * log* n)，我们总共有n^2 * (n^2 - 1) / 2条遍，union find的每次操作时间复杂度为O(log* n)，空间复杂度O(n^2)，代码如下：

	class Solution {
	public:
	int swimInWater(vector<vector<int>>& grid) {
	int m = grid.size(), n = m ? grid[0].size() : 0;
	m_sz = vector<int>(m * n, 1);
	m_uf = vector<int>(m * n, 0);
	for (int i = 0; i < m * n; ++i)m_uf[i] = i;
	unordered_map<int, set<pair<int, int>>> edges;
	pair<int, int> dirs[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
	for (int i = 0; i < m; ++i)
	{
	for (int j = 0; j < n; ++j)
	{
	for (int k = 0; k < 4; ++k)
	{
	int x = i + dirs[k].first, y = j + dirs[k].second;
	if (x >= 0 && x < m && y >= 0 && y < n && grid[i][j] >= grid[x][y])
	edges[grid[i][j]].insert(make_pair(x * n + y, i * n + j));
	}
	}
	}
	int height = 0;
	while (height < m * n)
	{
	for (auto& edge : edges[height])
	connect(edge.first, edge.second);
	if (find(0, m * n - 1))break;
	++height;
	}
	return height;
	}
	private:
	vector<int> m_uf;
	vector<int> m_sz;
	void connect(int i, int j)
	{
	int rootI = root(i), rootJ = root(j);
	if(rootI == rootJ)return;
	if (m_sz[rootI] <= m_sz[rootJ])
	{
	m_uf[rootI] = rootJ;
	m_sz[rootJ] += m_sz[rootI];
	}
	else
	{
	m_uf[rootJ] = rootI;
	m_sz[rootI] += m_sz[rootJ];
	}
	}
	bool find(int i, int j)
	{
	return root(i) == root(j);
	}
	int root(int i)
	{
	if (m_uf[i] == i)return i;
	int r = root(m_uf[i]);
	m_uf[i] = r;
	return r;
	}
	};

view raw Swim in Rising Water_uf.cpp hosted with ❤ by GitHub

可以看到Union Find方法的某些缺点，如果高度的范围太大，union find就会很不效率。但是这也给我们提供了一个很好的思路，为什么我们要顺序的搜索最小的高度呢？如果我们binary search，显然我们知道答案所在的范围为[minHeignt, maxHeignt]，我们也有O(n^2)的方法来验证给定height，从起点能否到终点。显然二分也是一个很好的方法，时间复杂O(n^2 * log(n))，空间复杂度 worst case O(n^2)，代码如下：

	class Solution {
	public:
	int swimInWater(vector<vector<int>>& grid) {
	int m = grid.size(), n = m? grid[0].size(): 0, lo = n && m? grid[0][0]: 0, hi = m * n - 1;
	while(lo < hi)
	{
	int mid = lo + (hi - lo) / 2;
	unordered_set<int> visited;
	if(canReach(grid, mid, 0, m * n - 1, visited))
	hi = mid;
	else
	lo = mid + 1;
	}
	return lo;
	}
	private:
	bool canReach(vector<vector<int>>& grid, int t, int curr, int target, unordered_set<int>& visited)
	{
	int m = grid.size(), n = m? grid[0].size(): 0, i = curr / n, j = curr % n;
	if(curr == m * n - 1)return true;
	visited.insert(curr);
	pair<int, int> dirs[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	for(int k = 0; k < 4; ++k)
	{
	int x = i + dirs[k].first, y = j + dirs[k].second;
	if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] <= t && visited.find(x * n + y) == visited.end())
	{
	if(canReach(grid, t, x * n + y, target, visited))return true;
	}
	}
	return false;
	}
	};

view raw Swim in Rising Water_bs.cpp hosted with ❤ by GitHub

除此之外我们还有用类似Dijkstra的解法。我们用f(v)表示从起点到当前节点v所经过的最大高度，我们可以看出f(v)是沿路径递增的。那么我们可以用类似的方法证明Dijkstra也可以用来求到节点v的最小f(v)的值，证明如下：

• 对于v = start node，显而易见最小的f(v)就是起始节点的高度
• 假设存在set = {v1, v2,...,vi}，我们求得了set中所有节点的最小f(v)值。那么对于我们即将从priority queue上展开的下一个节点vk，其对应的值就是最小的f(vk)值
• 我们可以明确的是priority queue上对应的值，是set中所有路径到达vk的最小f(vk)值
• 假设存在另一条路径通过set之外某个节点vj到达vk，并且这条路径上的f(vk)值比priority queue上对应的值要小。那么由于f(v)在路径上是递增的，那么显然vj要比vk更先被展开，这与我们的假设“vj是set之外的某个节点”矛盾

时间复杂度O(n^2 log n)，最坏的情况可能展开n^2个node，时间复杂度O(n^2)，代码如下：

	class Solution {
	public:
	int swimInWater(vector<vector<int>>& grid) {
	int n = grid.size(), target = n * n - 1, res = 0;
	if(!n)return 0;
	//we can use the same way to prove dijkstra also works for this problem
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push(make_pair(grid[0][0], 0));
	pair<int, int> dirs[4] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
	unordered_set<int> visited;
	while(visited.size() < n * n)
	{
	auto p = pq.top();
	pq.pop();
	if(visited.find(p.second) != visited.end())continue;
	visited.insert(p.second);
	//dijkstar adds result from smallerst to largest
	res = max(res, p.first);
	if(p.second == target)return res;
	int path = p.first, i = p.second / n, j = p.second % n;
	for(int k = 0; k < 4; ++k)
	{
	int x = i + dirs[k].first, y = j + dirs[k].second;
	if(x >= 0 && x < n && y >= 0 && y < n && visited.find(p.second) != visited.end())
	pq.push(make_pair(grid[x][y], x * n + y));
	}
	}
	return -1;
	}
	};

view raw Swim in Rising Water_dj.cpp hosted with ❤ by GitHub