[LeetCode]01 Matrix

两种做法。求最短距离的显然BFS可以解，然后DP从左上到右下再从右下到左上也可以解。
假设输入matrix为m * n，BFS解法时间O(m * n)，空间O(m * n)，代码如下：

	class Solution {
	public:
	vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
	int m = matrix.size(), n = m? matrix[0].size(): 0;
	queue<int> q;
	vector<pair<int, int>> dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
	for(int i = 0; i < m; ++i)
	{
	for(int j = 0; j < n; ++j)
	{
	if(matrix[i][j])matrix[i][j] = -1;
	else q.push(i * n + j);
	}
	}
	int layer = 0;
	while(q.size())
	{
	int len = q.size();
	while(len--)
	{
	int num = q.front(), i = num / n, j = num % n;
	q.pop();
	for(auto&& dir : dirs)
	{
	int x = i + dir.first, y = j + dir.second;
	if(x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] == -1)
	{
	q.push(x * n + y);
	matrix[x][y] = layer + 1;
	}
	}
	}
	++layer;
	}
	return matrix;
	}
	};

view raw 01 Matrix_1.cpp hosted with ❤ by GitHub

DP做法时间O(m * n)，空间O(1)，代码如下：

	class Solution {
	public:
	vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
	int m = matrix.size(), n = m? matrix[0].size(): 0;
	for(int i = 0; i < m; ++i)
	{
	for(int j = 0; j < n; ++j)
	{
	if(matrix[i][j])
	{
	int up = i? matrix[i - 1][j]: m + n, left = j? matrix[i][j - 1]: m + n;
	matrix[i][j] = min(up, left) + 1;
	}
	}
	}
	for(int i = m - 1; i >= 0; --i)
	{
	for(int j = n - 1; j >= 0; --j)
	{
	if(matrix[i][j])
	{
	int bottom = i < m - 1? matrix[i + 1][j]: m + n, right = j < n - 1? matrix[i][j + 1]: m + n;
	matrix[i][j] = min(matrix[i][j], min(bottom, right) + 1);
	}
	}
	}
	return matrix;
	}
	};

view raw 01 Matrix_2.cpp hosted with ❤ by GitHub