Archives/01_matrix.cpp at master · shafitek/Archives · GitHub

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
// https://leetcode.com/problems/01-matrix/

class Solution
{
public:
    int m, n;
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};
    vector<vector<int>> updateMatrix(vector<vector<int>> &matrix)
    {
        m = matrix.size();
        n = matrix[0].size();
        vector<vector<int>> memo(m, vector<int>(n, 0));

        queue<vector<int>> q;

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (matrix[i][j] == 0)
                {
                    q.push({i, j});
                }
                else
                {
                    memo[i][j] = INT_MAX;
                }
            }
        }

        int x, y, nx, ny, distance = 0;
        while (!q.empty())
        {
            vector<int> node = q.front();
            x = node[0];
            y = node[1];
            q.pop();

            for (int i = 0; i < 4; i++)
            {
                int nx = node[0] + dx[i], ny = node[1] + dy[i];
                distance = memo[x][y] + 1;

                if (nx < 0 || nx >= m || ny < 0 || ny >= n || matrix[nx][ny] == 0 || distance >= memo[nx][ny])
                    continue;

                memo[nx][ny] = distance;
                q.push({nx, ny});
            }
        }

        return memo;
    }

    void PrintMatrix(vector<vector<int>> &matrix)
    {
        for (int i = 0; i < matrix.size(); i++)
        {
            cout << "| ";
            for (int j = 0; j < matrix[0].size(); j++)
            {
                cout << matrix[i][j] << " | ";
            }
            cout << endl;
        }
        cout << "---" << endl;
    }
};

// TLE! INCOMPLETE!
// class Solution
// {
// public:
//     vector<vector<int>> updateMatrix(vector<vector<int>> &matrix)
//     {
//         vector<vector<int>> memo(matrix.size(), vector<int>(matrix[0].size()));
//         for (int i = 0; i < matrix.size(); i++)
//         {
//             for (int j = 0; j < matrix[0].size(); j++)
//             {
//                 if (matrix[i][j] == 1)
//                     memo[i][j] = INT_MAX;
//             }
//         }

//         for (int i = 0; i < matrix.size(); i++)
//         {
//             for (int j = 0; j < matrix[0].size(); j++)
//             {
//                 if (matrix[i][j] == 1)
//                     continue;
//                 dfs(matrix, memo, i - 1, j, 1);
//                 dfs(matrix, memo, i, j + 1, 1);
//                 dfs(matrix, memo, i + 1, j, 1);
//                 dfs(matrix, memo, i, j - 1, 1);
//             }
//         }

//         return memo;
//     }

//     void dfs(vector<vector<int>> &matrix, vector<vector<int>> &memo, int i, int j, int count)
//     {
//         if (i >= 0 && i < matrix.size() && j >= 0 && j < matrix[0].size() && count < memo[i][j])
//         {
//             memo[i][j] = count;
//             dfs(matrix, memo, i - 1, j, count + 1);
//             dfs(matrix, memo, i, j + 1, count + 1);
//             dfs(matrix, memo, i + 1, j, count + 1);
//             dfs(matrix, memo, i, j - 1, count + 1);
//         }
//     }

//     void PrintMatrix(vector<vector<int>> &matrix)
//     {
//         for (int i = 0; i < matrix.size(); i++)
//         {
//             cout << "| ";
//             for (int j = 0; j < matrix[0].size(); j++)
//             {
//                 cout << matrix[i][j] << " | ";
//             }
//             cout << endl;
//         }
//     }
// };