Coding Test/LeetCode
[LeetCode] 542. 01 Matrix c++
owls
2023. 1. 3. 17:15
728x90
문제
Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.
문제 해결
벡터값 초기화 값을 INT8_MAX로 하니 최대값이 127이라 fail이 나왔다.
- 1 <= m, n <= 10^4
정수 범위가 작아서 난 오류라 범위를 더 크게 설정하였다. INT16_MAX로 변경하니 성공!
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
vector<vector<int>> res(m, vector<int>(n, INT16_MAX));
queue<pair<int, int>> q;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(mat[i][j] == 0){
res[i][j] = 0;
q.push({i, j});
}
}
}
vector<pair<int, int>> dirs{ {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
while(!q.empty()){
auto cur = q.front();
q.pop();
int curx = cur.first;
int cury = cur.second;
for(auto dir : dirs){
int x = curx + dir.first;
int y = cury + dir.second;
if( x >= 0 && x < m && y >= 0 && y < n){
if(res[x][y] > res[curx][cury] + 1){
res[x][y] = res[curx][cury] + 1;
q.push({x, y});
}
}
}
}
return res;
}
};
728x90