542.01-矩阵/*struct coord { int x; int y; coord(int x, int y) : x(x), y(y) {}};*/class Solution { public: /*vector<vector<int>> updateMatrix(vector<vector<int>> &mat) { vector<bool> visitedx(mat[0].size(), 0); vector<vector<bool>> visited(mat.size(), visitedx); for (int i = 0; i < mat.size(); i++) { for (int j = 0; j < mat[0].size(); j++) { for (int h = 0; h < mat.size(); h++) { for (int k = 0; k < mat[0].size(); k++) { visited[h][k] = 0; } } mat[i][j] = BFS(mat, i, j, visited); } } return mat; } int BFS(vector<vector<int>> &mat, int i, int j, vector<vector<bool>> visited) { if (i < 0 || j < 0 || i > mat.size() - 1 || j > mat[0].size() - 1) return 10001; if (mat[i][j] == 0) return 0; if (visited[i][j]) return INT_MAX; visited[i][j] = 1; return 1 + min(min(BFS(mat, i + 1, j, visited), BFS(mat, i, j + 1, visited)), min(BFS(mat, i - 1, j, visited), BFS(mat, i, j - 1, visited))); }*/ //超出范围：INT_MAX太搞了 //顺带一提，错误逻辑 //官方解题是从0搜1的woc /*vector<vector<int>> updateMatrix(vector<vector<int>> &matrix) { /*queue<coord> search; vector<vector<bool>> visited(mat.size(), vector<bool>(mat.size(), 0)); for (int i = 0; i < mat.size(); i++) { for (int j = 0; j < mat[0].size(); j++) { if (mat[i][j] == 0) { search.push(coord(i, j)); visited[i][j] = 1; } } } while (!search.empty()) { coord temp = search.front(); search.pop(); if (temp.x > 0 && mat[temp.x - 1][temp.y] == 1 && visited[temp.x - 1][temp.y] == 0) { mat[temp.x - 1][temp.y] += mat[temp.x][temp.y]; visited[temp.x - 1][temp.y] = 1; search.push(coord(temp.x - 1, temp.y)); } if (temp.x < mat.size() - 1 && mat[temp.x + 1][temp.y] == 1 && visited[temp.x + 1][temp.y] == 0) { mat[temp.x + 1][temp.y] += mat[temp.x][temp.y]; visited[temp.x + 1][temp.y] = 1; search.push(coord(temp.x + 1, temp.y)); } if (temp.y > 0 && mat[temp.x][temp.y - 1] == 1 && visited[temp.x][temp.y - 1] == 0) { mat[temp.x][temp.y - 1] += mat[temp.x][temp.y]; visited[temp.x][temp.y - 1] = 1; search.push(coord(temp.x, temp.y - 1)); } if (temp.y < mat[0].size() - 1 && mat[temp.x][temp.y + 1] == 1 && visited[temp.x][temp.y + 1] == 0) { mat[temp.x][temp.y + 1] += mat[temp.x][temp.y]; visited[temp.x][temp.y + 1] = 1; search.push(coord(temp.x, temp.y + 1)); } } return mat;}*/ //加了很多冗余变量 /*vector<vector<int>> updateMatrix(vector<vector<int>> &matrix) { vector<vector<int>> dp(matrix.size(), vector<int>(matrix[0].size(), INT_MAX - 1)); for (int i = 0; i < matrix.size(); i++) for (int j = 0; j < matrix[0].size(); j++) { if (matrix[i][j] == 0) dp[i][j] = 0; } for (int i = 0; i < matrix.size(); i++) for (int j = 0; j < matrix[0].size(); j++) { if (i > 0) dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1); if (j > 0) dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1); } //四个方位中已经遍历过的两个方位(注意+1) for (int i = matrix.size() - 1; i >= 0; i--) for (int j = matrix[0].size() - 1; j >= 0; j--) { //反过来遍历 if (i < matrix.size() - 1) dp[i][j] = min(dp[i][j], dp[i + 1][j] + 1); if (j < matrix[0].size() - 1) dp[i][j] = min(dp[i][j], dp[i][j + 1] + 1); } //剩下的两个方位 return dp; // 50/50 cases passed (56 ms) // Your runtime beats 92.26 % of cpp submissions // Your memory usage beats 93.22 % of cpp submissions (26.7 MB) }*/ vector<vector<int>> updateMatrix(vector<vector<int>> &mat) { queue<vector<int>> coord; for (int i = 0; i < mat.size(); i++) { for (int j = 0; j < mat[0].size(); j++) { if (mat[i][j] == 0) { coord.push({i, j}); } else mat[i][j] = INT_MAX - 1; //化身成为未完成的距离数组（到0的距离） } } while (!coord.empty()) { vector<int> temp = coord.front(); coord.pop(); if (temp[0] > 0 && mat[temp[0]][temp[1]] + 1 < mat[temp[0] - 1][temp[1]]) { //前面是mat[temp[0] - 1][temp[1]]到中心（mat[temp[0]][temp[1]]）的距离，所以加了1 mat[temp[0] - 1][temp[1]] = mat[temp[0]][temp[1]] + 1; coord.push({temp[0] - 1, temp[1]}); } if (temp[0] < mat.size() - 1 && mat[temp[0]][temp[1]] + 1 < mat[temp[0] + 1][temp[1]]) { mat[temp[0] + 1][temp[1]] = mat[temp[0]][temp[1]] + 1; coord.push({temp[0] + 1, temp[1]}); } if (temp[1] > 0 && mat[temp[0]][temp[1]] + 1 < mat[temp[0]][temp[1] - 1]) { mat[temp[0]][temp[1] - 1] = mat[temp[0]][temp[1]] + 1; coord.push({temp[0], temp[1] - 1}); } if (temp[1] < mat[0].size() - 1 && mat[temp[0]][temp[1]] + 1 < mat[temp[0]][temp[1] + 1]) { mat[temp[0]][temp[1] + 1] = mat[temp[0]][temp[1]] + 1; coord.push({temp[0], temp[1] + 1}); } } return mat; } // 50/50 cases passed (168 ms) // Your runtime beats 5.88 % of cpp submissions // Your memory usage beats 5.03 % of cpp submissions (54.2 MB) //使用INT_MAX来避免visited数组}; 994.腐烂的橘子class Solution { public: int orangesRotting(vector<vector<int>> &grid) { int Max = 0; queue<vector<int>> coord; for (int i = 0; i < grid.size(); i++) { for (int j = 0; j < grid[0].size(); j++) { if (grid[i][j] == 2) coord.push({i, j}); } } /* while (!coord.empty()) { vector<int> temp = coord.front(); coord.pop(); Max = max(Max, grid[temp[0]][temp[1]]); if (temp[0] > 0 && grid[temp[0] - 1][temp[1]] == 1) { grid[temp[0] - 1][temp[1]] = grid[temp[0]][temp[1]] + 1; coord.push({temp[0] - 1, temp[1]}); } if (temp[0] < grid.size() - 1 && grid[temp[0] + 1][temp[1]] == 1) { grid[temp[0] + 1][temp[1]] = grid[temp[0]][temp[1]] + 1; coord.push({temp[0] + 1, temp[1]}); } if (temp[1] > 0 && grid[temp[0]][temp[1] - 1] == 1) { grid[temp[0]][temp[1] - 1] = grid[temp[0]][temp[1]] + 1; coord.push({temp[0], temp[1] - 1}); } if (temp[1] < grid[0].size() - 1 && grid[temp[0]][temp[1] + 1] == 1) { grid[temp[0]][temp[1] + 1] = grid[temp[0]][temp[1]] + 1; coord.push({temp[0], temp[1] + 1}); } }*/ int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}; while (!coord.empty()) { vector<int> temp = coord.front(); coord.pop(); for (int i = 0; i < 4; i++) { int x = temp[0] + dx[i], y = temp[1] + dy[i]; if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size()) continue; if (grid[x][y] == 0) continue; if (grid[x][y] != 1) continue; grid[x][y] = grid[temp[0]][temp[1]] + 1; coord.push({x, y}); } } // 306/306 cases passed (4 ms) // Your runtime beats 90.47 % of cpp submissions // Your memory usage beats 7.29 % of cpp submissions (13.3 MB) //酱汁循环，舍去if for (int i = 0; i < grid.size(); i++) { for (int j = 0; j < grid[0].size(); j++) { if (grid[i][j] == 1) return -1; Max = max(Max, grid[i][j]); } } return max(0, Max - 2); } // 306/306 cases passed (4 ms) // Your runtime beats 90.47 % of cpp submissions // Your memory usage beats 8.46 % of cpp submissions (13.3 MB) /*int orangesRotting(vector<vector<int>> &grid) { int Min = INT_MAX; int Max = 0; for (int i = 0; i < grid.size(); i++) { for (int j = 0; j < grid[0].size(); j++) { if (grid[i][j] == 1) { int temp = max(i > 0 ? grid[i - 1][j] : 0, j > 0 ? grid[i][j - 1] : 0); grid[i][j] = temp > 1 ? temp + grid[i][j] : 1; } Max = max(Max, grid[i][j]); } } for (int i = grid.size() - 1; i >= 0; i--) { for (int j = grid[0].size() - 1; j >= 0; j--) { if (grid[i][j] == 1) { int temp = max(i < grid.size() - 1 ? grid[i + 1][j] : 0, j < grid[0].size() - 1 ? grid[i][j + 1] : 0); grid[i][j] = temp > 1 ? temp + grid[i][j] : 1; Min = min(Min, grid[i][j]); } Max = max(Max, grid[i][j]); } } return Min == 1 ? -1 : max(0, Max - 2); }*/ //逻辑错误，比如： /* 2 0 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 1 1 0 1 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 0 0 0 0 1 0 1 1 0 1 1 1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 */ //最后只能 /* 2 0 36 35 34 33 32 31 30 29 3 0 1 0 0 0 0 0 0 28 4 0 1 0 1 1 1 1 0 27 5 0 1 0 1 0 0 1 0 26 6 0 1 0 1 0 0 1 0 25 7 0 1 0 1 1 0 1 0 24 8 0 1 0 0 0 0 1 0 23 9 0 1 1 1 1 1 1 0 22 10 0 0 0 0 0 0 0 0 21 11 12 13 14 15 16 17 18 19 20 */};
%E2%9C%A7Great%20Crisis%20II.jpg)