1568. Minimum Number of Days to Disconnect Island

class Solution {
public:
    int minDays(vector<vector<int>>& grid) {
        if (isDisconnected(grid)) return 0;

        int m = grid.size();
        int n = grid[0].size();

        // Try removing one cell
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    grid[i][j] = 0;
                    if (isDisconnected(grid)) return 1;
                    grid[i][j] = 1;
                }
            }
        }

        // Try removing two cells
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    grid[i][j] = 0;
                    for (int x = 0; x < m; ++x) {
                        for (int y = 0; y < n; ++y) {
                            if (grid[x][y] == 1) {
                                grid[x][y] = 0;
                                if (isDisconnected(grid)) return 2;
                                grid[x][y] = 1;
                            }
                        }
                    }
                    grid[i][j] = 1;
                }
            }
        }
        return 2;
    }

private:
    bool isDisconnected(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> visited(m, vector<int>(n, 0));

        int landCount = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    ++landCount;
                    if (!visited[i][j]) {
                        if (landCount > 1) return true;
                        bfs(grid, visited, i, j);
                    }
                }
            }
        }
        return landCount == 0;
    }

    void bfs(vector<vector<int>>& grid, vector<vector<int>>& visited, int i, int j) {
        int m = grid.size();
        int n = grid[0].size();
        queue<pair<int, int>> q;
        q.push({i, j});
        visited[i][j] = 1;

        vector<int> dirX = {-1, 1, 0, 0};
        vector<int> dirY = {0, 0, -1, 1};

        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();

            for (int d = 0; d < 4; ++d) {
                int newX = x + dirX[d];
                int newY = y + dirY[d];
                if (newX >= 0 && newX < m && newY >= 0 && newY < n && grid[newX][newY] == 1 && !visited[newX][newY]) {
                    visited[newX][newY] = 1;
                    q.push({newX, newY});
                }
            }
        }
    }
};