leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0417.cpp (1474B)

0 class Solution { 1 typedef vector<vector<int>> Matrix; 2 typedef vector<vector<bool>> Marked; 3 typedef queue<pair<int, int>> Queue; 4 const vector<pair<int, int>> offsets = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; 5 6 int n, m; 7 int valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; } 8 9 void dfs(Matrix &mat, Marked &mark, int x, int y) { 10 if (mark[x][y]) return; 11 Queue q; 12 13 q.push({x, y}), mark[x][y] = true; 14 while (!q.empty()) { 15 auto [a, b] = q.front(); 16 q.pop(); 17 for (auto [oa, ob] : offsets) { 18 int x = a + oa, y = b + ob; 19 if (!valid(x, y) || mark[x][y] || mat[x][y] < mat[a][b]) continue; 20 mark[x][y] = true; 21 q.push({x, y}); 22 } 23 } 24 } 25 26 public: 27 vector<vector<int>> pacificAtlantic(Matrix &heights) { 28 n = heights.size(), m = heights[0].size(); 29 Marked pac(n, vector<bool>(m, false)), atl(n, vector<bool>(m, false)); 30 31 for (int i = 0; i < n; i++) { 32 dfs(heights, pac, i, 0); 33 dfs(heights, atl, i, m - 1); 34 } 35 36 for (int i = 0; i < m; i++) { 37 dfs(heights, pac, 0, i); 38 dfs(heights, atl, n - 1, i); 39 } 40 41 vector<vector<int>> res; 42 for (int i = 0; i < n; i++) 43 for (int j = 0; j < m; j++) 44 if (pac[i][j] && atl[i][j]) res.push_back({i, j}); 45 46 return res; 47 } 48 };