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