leetcode

0 class Solution {

1 bool isDisconected(const vector<vector<int>> &grid) const {

2 const int n = size(grid), m = size(grid[0]);

3 bool seen = false;

4

5 static int visit[31][31];

6 memset(visit, 0x00, sizeof(visit));

7

8 queue<pair<int, int>> q;

9 for (int i = 0; i < n; i++) {

10 for (int j = 0; j < m; j++) {

11 if (!grid[i][j] || visit[i][j]) continue;

12 if (seen) return true;

13 seen = true;

14

15 q.emplace(i, j);

16 while (!q.empty()) {

17 const auto [a, b] = q.front();

18 q.pop();

19

20 static const int dir[] = {-1, 0, 1, 0, -1};

21 for (int k = 0; k < 4; k++) {

22 const int x = a + dir[k];

23 const int y = b + dir[k + 1];

24

25 if (x < 0 || y < 0 || x >= n || y >= m) continue;

26 if (!grid[x][y] || visit[x][y]) continue;

27 q.emplace(x, y);

28 visit[x][y] = 1;

29 }

30 }

31 }

32 }

33

34 return !seen;

35 }

36

37 public:

38 int minDays(vector<vector<int>> &grid) const {

39 const int n = size(grid), m = size(grid[0]);

40

41 if (isDisconected(grid)) return 0;

42 for (int i = 0; i < n; i++) {

43 for (int j = 0; j < m; j++) {

44 if (!grid[i][j]) continue;

45

46 grid[i][j] = 0;

47 if (isDisconected(grid)) return 1;

48 grid[i][j] = 1;

49 }

50 }

51

52 return 2;

53 }

54 };