542. 01 Matrix

https://leetcode.com/problems/01-matrix?envType=problem-list-v2&envId=rabvlt31

熊熊發現最近我好像特愛暴力法...這題我的解法就是暴力破解，沒什麼含金量，程式碼又臭又長，beat 5%的 runtime and memory，昏了都。

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();
        vector ans(m, vector<int>(n, std::numeric_limits<int>::max()));
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(mat[i][j] == 0) {
                    ans[i][j] = 0;
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(ans[i][j] == 0) {
                    updateSurround(ans, i, j, m, n);
                }
                
            }
        }

        return ans;
    }
    void updateSurround(vector<vector<int>>& ans, int x, int y, int& m, int& n) {
        
        if(x - 1 >= 0) {
            if(ans[x-1][y] > ans[x][y] + 1) {
                ans[x-1][y] = ans[x][y] + 1;
                updateSurround(ans, x-1, y, m, n);
            }
        }

        if(x + 1 < m) {
            if(ans[x+1][y] > ans[x][y] + 1) {
                ans[x+1][y] = ans[x][y] + 1;
                updateSurround(ans, x+1, y, m, n);
            }
        }

        if(y - 1 >= 0) {
            if(ans[x][y-1] > ans[x][y] + 1) {
                ans[x][y-1] = ans[x][y] + 1;
                updateSurround(ans, x, y-1, m, n);
            }
        }

        if(y + 1 < n) {
            if(ans[x][y+1] > ans[x][y] + 1) {
                ans[x][y+1] = ans[x][y] + 1;
                updateSurround(ans, x, y+1, m, n);
            }
        }
    }
};

當然純純的暴力法是過不了的，會 TLE。我這邊的做法是要先把所有 0 填進去，再來暴力法會減少很多時間。針對每個是 0 的 cell 擴展更新。

Best Solution

class Solution {
public:
    vector<int> DIR = {0, 1, 0, -1, 0};
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {

        int m = mat.size(), n = mat[0].size();
        
        queue<pair<int, int>> q;
        for (int r = 0; r < m; ++r)
            for (int c = 0; c < n; ++c)
                if (mat[r][c] == 0) q.emplace(r, c);
                else mat[r][c] = -1; // Marked as not processed yet!

        while (!q.empty()) {
            auto [r, c] = q.front(); q.pop();
            for (int i = 0; i < 4; ++i) {
                int nr = r + DIR[i], nc = c + DIR[i+1];
                if (nr < 0 || nr == m || nc < 0 || nc == n || mat[nr][nc] != -1) continue;
                mat[nr][nc] = mat[r][c] + 1;
                q.emplace(nr, nc);
            }
        }
        return mat;
    }
};

優雅！！真是太優雅了！！這個 solution 用了 queue 來 maintain 更新的過程，某種程度上來講是 BFS，保證每個 cell 被 遍歷到的時候更新都會直接是答案，原因就是離 0 較近的 cell 會先被遍歷到！！聰明太聰明了。

這個 solution 讓我複習了 queue 的用法。除了演算法很聰明外，這個作者也用了 emplace 來取代一些不必要的變數複製與移動等。非常聰明的做法，甚至 memory 不用重新宣告。