Fork me on GitHub

01 Matrix

Posted on

Description

https://leetcode.com/problems/01-matrix/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int rowSize = matrix.size();
        if (rowSize == 0) return matrix;
        int columnSize = matrix[0].size();
        
        vector<vector<int>> ret(rowSize, vector<int>(columnSize));
        
        for (int i = 0; i < rowSize; ++i) {
            for (int j = 0; j < columnSize; ++j) {
                ret[i][j] = findShortestPath(matrix, i, j, rowSize, columnSize);
            }
        }
        return ret;
    }
    
    int findShortestPath(vector<vector<int>>& matrix, int i, int j, int rowSize, int columnSize) {
        if (matrix[i][j] == 0) return 0; 
        queue<pair<int, pair<int, int>>> q;
        vector<pair<int, int>> directions = {
            {-1, 0}, {1, 0}, {0, -1}, {0, 1}
        };
        q.push(make_pair(1, make_pair(i, j)));
        while (!q.empty()) {
            int depth = q.front().first;
            int curRow = q.front().second.first;
            int curCol = q.front().second.second;
            q.pop();
            for (auto& item : directions) {
                int newRow = curRow + item.first;
                int newColumn = curCol + item.second;
                if (newRow < 0 || newRow >= rowSize || 
                     newColumn < 0 || newColumn >= columnSize) continue;
                if (matrix[newRow][newColumn] == 0) return depth;
                else {
                    q.push(make_pair(depth + 1, make_pair(newRow, newColumn)));
                }
            }
        }
        return -1;// Invaid 
    }
};