1568.cpp (1616B)
1 class Solution { 2 bool isDisconected(const vector<vector<int>> &grid) const { 3 const int n = size(grid), m = size(grid[0]); 4 bool seen = false; 5 6 static int visit[31][31]; 7 memset(visit, 0x00, sizeof(visit)); 8 9 queue<pair<int, int>> q; 10 for (int i = 0; i < n; i++) { 11 for (int j = 0; j < m; j++) { 12 if (!grid[i][j] || visit[i][j]) continue; 13 if (seen) return true; 14 seen = true; 15 16 q.emplace(i, j); 17 while (!q.empty()) { 18 const auto [a, b] = q.front(); 19 q.pop(); 20 21 static const int dir[] = {-1, 0, 1, 0, -1}; 22 for (int k = 0; k < 4; k++) { 23 const int x = a + dir[k]; 24 const int y = b + dir[k + 1]; 25 26 if (x < 0 || y < 0 || x >= n || y >= m) continue; 27 if (!grid[x][y] || visit[x][y]) continue; 28 q.emplace(x, y); 29 visit[x][y] = 1; 30 } 31 } 32 } 33 } 34 35 return !seen; 36 } 37 38 public: 39 int minDays(vector<vector<int>> &grid) const { 40 const int n = size(grid), m = size(grid[0]); 41 42 if (isDisconected(grid)) return 0; 43 for (int i = 0; i < n; i++) { 44 for (int j = 0; j < m; j++) { 45 if (!grid[i][j]) continue; 46 47 grid[i][j] = 0; 48 if (isDisconected(grid)) return 1; 49 grid[i][j] = 1; 50 } 51 } 52 53 return 2; 54 } 55 };