1568 - Minimum Number of Days to Disconnect Island

 JAVA

• class Solution {
      private static final int[] DIRS = new int[] {-1, 0, 1, 0, -1};
      private int[][] grid;
      private int m;
      private int n;
  
      public int minDays(int[][] grid) {
          this.grid = grid;
          m = grid.length;
          n = grid[0].length;
          if (count() != 1) {
              return 0;
          }
          for (int i = 0; i < m; ++i) {
              for (int j = 0; j < n; ++j) {
                  if (grid[i][j] == 1) {
                      grid[i][j] = 0;
                      if (count() != 1) {
                          return 1;
                      }
                      grid[i][j] = 1;
                  }
              }
          }
          return 2;
      }
  
      private int count() {
          int cnt = 0;
          for (int i = 0; i < m; ++i) {
              for (int j = 0; j < n; ++j) {
                  if (grid[i][j] == 1) {
                      dfs(i, j);
                      ++cnt;
                  }
              }
          }
          for (int i = 0; i < m; ++i) {
              for (int j = 0; j < n; ++j) {
                  if (grid[i][j] == 2) {
                      grid[i][j] = 1;
                  }
              }
          }
          return cnt;
      }
  
      private void dfs(int i, int j) {
          grid[i][j] = 2;
          for (int k = 0; k < 4; ++k) {
              int x = i + DIRS[k], y = j + DIRS[k + 1];
              if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
                  dfs(x, y);
              }
          }
      }
  }

C++

• class Solution {
  public:
      const vector<int> dirs = {-1, 0, 1, 0, -1};
      int m, n;
  
      int minDays(vector<vector<int>>& grid) {
          m = grid.size(), n = grid[0].size();
          if (count(grid) != 1) {
              return 0;
          }
          for (int i = 0; i < m; ++i) {
              for (int j = 0; j < n; ++j) {
                  if (grid[i][j] == 1) {
                      grid[i][j] = 0;
                      if (count(grid) != 1) {
                          return 1;
                      }
                      grid[i][j] = 1;
                  }
              }
          }
          return 2;
      }
  
      int count(vector<vector<int>>& grid) {
          int cnt = 0;
          for (int i = 0; i < m; ++i) {
              for (int j = 0; j < n; ++j) {
                  if (grid[i][j] == 1) {
                      dfs(i, j, grid);
                      ++cnt;
                  }
              }
          }
          for (int i = 0; i < m; ++i) {
              for (int j = 0; j < n; ++j) {
                  if (grid[i][j] == 2) {
                      grid[i][j] = 1;
                  }
              }
          }
          return cnt;
      }
  
      void dfs(int i, int j, vector<vector<int>>& grid) {
          grid[i][j] = 2;
          for (int k = 0; k < 4; ++k) {
              int x = i + dirs[k], y = j + dirs[k + 1];
              if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
                  dfs(x, y, grid);
              }
          }
      }
  };