[LeetCode]Largest Plus Sign

对于一个点，我么分别总四个方向确定其arm的长度，然后取所有方向最小的就是这个位置plus sign的order。计算arm长度的话可以用dp的思路，我们用求left arm举例，递推公式为:

• dp[i][j] = dp[i][j - 1] + 1, if matrix[i][j] == 1
• else, dp[i][j] = 0

其他方向的同理。时间空间复杂度均为O(N ^ 2)，代码如下：

	class Solution {
	public:
	int orderOfLargestPlusSign(int N, vector<vector<int>>& mines) {
	//dp[i][j] represent longest plus sign wih only left arms with centern at i j
	//dp[i][j] = mindp[i][j - 1] + 1, if matrix[i][j] is 1
	//else dp[i][j] = 0;
	//up, bottom and right arms are similar
	vector<vector<int>> dp(N, vector<int>(N, 0));
	//i * N + j
	unordered_set<int> set;
	for (auto& mine : mines)set.insert(mine[0] * N + mine[1]);
	//bottom
	for (int i = N - 1; i >= 0; --i)
	{
	for (int j = N - 1; j >= 0; --j)
	{
	int key = i * N + j;
	if (set.find(key) != set.end())
	dp[i][j] = 0;
	else
	dp[i][j] = i == N - 1? 1 : dp[i + 1][j] + 1;
	}
	}
	//right
	vector<int> cnts(N, 0);
	for (int j = N - 1; j >= 0; --j)
	{
	for (int i = N - 1; i >= 0; --i)
	{
	int key = i * N + j, val = 0;
	if (set.find(key) != set.end())
	cnts[i] = 0;
	else
	cnts[i] = j == N - 1 ? 1 : cnts[i] + 1;
	dp[i][j] = min(dp[i][j], cnts[i]);
	}
	}
	//left
	for (int j = 0; j < N; ++j)
	{
	for (int i = 0; i < N; ++i)
	{
	int key = i * N + j, val = 0;
	if (set.find(key) != set.end())
	cnts[i] = 0;
	else
	cnts[i] = j == 0 ? 1 : cnts[i] + 1;
	dp[i][j] = min(dp[i][j], cnts[i]);
	}
	}
	int res = 0;
	//up
	for (int i = 0; i < N; ++i)
	{
	for (int j = 0; j < N; ++j)
	{
	int key = i * N + j, val = 0;
	if (set.find(key) != set.end())
	cnts[j] = 0;
	else
	cnts[j] = i == 0 ? 1 : cnts[j] + 1;
	dp[i][j] = min(dp[i][j], cnts[j]);
	res = max(res, dp[i][j]);
	}
	}
	return res;
	}
	};

view raw Largest Plus Sign.cpp hosted with ❤ by GitHub