[leetcode] 542. 01 Matrix (Medium)

给予一个矩阵，矩阵有1有0，计算每一个1到0需要走几步，只能走上下左右。

解法一：

利用dp，从左上角遍历一遍，再从右下角遍历一遍，dp存储当前位置到0的最短距离。

十分粗心的搞错了col和row，改了半天…………

Runtime: 132 ms, faster than 98.88% of C++ online submissions for 01 Matrix.

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

解法二：

BFS

class Solution
{
private:bool isValid(int m, int n, int x, int y){return x >= 0 && y >= 0 && x < m && y < n;}int getShortestDistance(int m, int n, int x, int y, vector<vector<int>> &distance){int result = distance[x][y];if (isValid(m, n, x, y + 1) && distance[x][y + 1] != INT_MAX){result = min(result, 1 + distance[x][y + 1]);}if (isValid(m, n, x, y - 1) && distance[x][y - 1] != INT_MAX){result = min(result, 1 + distance[x][y - 1]);}if (isValid(m, n, x + 1, y) && distance[x + 1][y] != INT_MAX){result = min(result, 1 + distance[x + 1][y]);}if (isValid(m, n, x - 1, y) && distance[x - 1][y] != INT_MAX){result = min(result, 1 + distance[x - 1][y]);}return result;}public:vector<vector<int>> updateMatrix(vector<vector<int>> &matrix){int m = matrix.size();int n = matrix[0].size();vector<vector<int>> distance(m, vector<int>(n, INT_MAX));queue<pair<int, int>> visit;for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){if (matrix[i][j] == 0){distance[i][j] = 0;visit.push(make_pair(i, j + 1));visit.push(make_pair(i, j - 1));visit.push(make_pair(i + 1, j));visit.push(make_pair(i - 1, j));}}}while (!visit.empty()){pair<int, int> cur = visit.front();visit.pop();int x = cur.first;int y = cur.second;if (isValid(m, n, x, y)){int shortestD = getShortestDistance(m, n, x, y, distance);if (shortestD < distance[x][y]){distance[x][y] = shortestD;visit.push(make_pair(x, y + 1));visit.push(make_pair(x, y - 1));visit.push(make_pair(x + 1, y));visit.push(make_pair(x - 1, y));}}}return distance;}
};