<p>You are given an <code>m x n</code> binary grid <code>grid</code> where <code>1</code> represents land and <code>0</code> represents water. An <strong>island</strong> is a maximal <strong>4-directionally</strong> (horizontal or vertical) connected group of <code>1</code>&#39;s.</p>

<p>The grid is said to be <strong>connected</strong> if we have <strong>exactly one island</strong>, otherwise is said <strong>disconnected</strong>.</p>

<p>In one day, we are allowed to change <strong>any </strong>single land cell <code>(1)</code> into a water cell <code>(0)</code>.</p>

<p>Return <em>the minimum number of days to disconnect the grid</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/24/land1.jpg" style="width: 500px; height: 169px;" />
<pre>
<strong>Input:</strong> grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]

<strong>Output:</strong> 2
<strong>Explanation:</strong> We need at least 2 days to get a disconnected grid.
Change land grid[1][1] and grid[0][2] to water and get 2 disconnected island.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/24/land2.jpg" style="width: 404px; height: 85px;" />
<pre>
<strong>Input:</strong> grid = [[1,1]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> Grid of full water is also disconnected ([[1,1]] -&gt; [[0,0]]), 0 islands.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 30</code></li>
	<li><code>grid[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
</ul>

#include <bits/stdc++.h>
using namespace std;
#define dbg(...) __f(#__VA_ARGS__,__VA_ARGS__)
// trace std::pair
template<class L,class R> std::ostream& operator<<(std::ostream& os,std::pair<L,R>& P){
    return os<<"{"<<P.first<<":"<<P.second<<"}";
}
// trace std::vector
template<class T> std::ostream& operator<<(std::ostream& os,std::vector<T>& V){
    os<<"[ ";for(auto v:V)os<<v<<" ";return os<<"]";
}
// trace std::map;
template<class L,class R> std::ostream& operator<<(std::ostream& os,std::map<L,R>& MP) {
    os<<"[ ";for(auto& P : MP) os<<P<<" ";return os<<"]";
}
// trace unordred_std::map
template<class L,class R> std::ostream& operator<<(std::ostream& os,std::unordered_map<L,R>& MP) {
    os<<"[ ";for(auto& P : MP) os<<P<<" ";return os<<"]";
}
// trace std::set
template<class T> std::ostream& operator<<(std::ostream& os,std::set<T>& S){
    os<<"[ ";for(auto s:S)os<<s<<" ";return os<<"]";
}
// trace std::unordered_set
template<class T> std::ostream& operator<<(std::ostream& os,std::unordered_set<T>& S){
    os<<"[ ";for(auto s:S)os<<s<<" ";return os<<"]";
}
// std::stack FUN
template<class T> void F_Stack(std::stack<T> st, std::string& cont) { 
    if(st.empty()) return;
    T mem=st.top();st.pop();F_Stack(st,cont);cont+=" "+to_string(mem);  
}
// trace std::stack                                                  
template<class T> std::ostream& operator<<(std::ostream& os,std::stack<T> st) {
    os<<"[";std::string cont="";F_Stack(st,cont);return os<<cont<<" ]";
}
// track std::queue
template<class T> std::ostream& operator<<(std::ostream& os,std::queue<T> q) {
    os<<"[ ";while(!q.empty()) os<<q.front()<<" ",q.pop();return os<<"]";
}

// for last arg.
template<typename Arg1>
void __f(const char* name,Arg1&& arg1){
    std::cout<<name<<" : "<<arg1<<std::endl;
}
// for variable arg
template <typename Arg1,typename... Args>
void __f(const char* names,Arg1&& arg1,Args&&... args){
    const char* comma=strchr(names+1,',');std::cout.write(names,comma-names)<<" : "<<arg1<<" | ";__f(comma+1,args...);
}

// dbg std::array
template<class T, size_t S> std::ostream& operator<<(std::ostream& os,std::array<T, S> V){
    os<<"[ ";for(auto v:V)os<<v<<" ";return os<<"]";
}

// X.find_by_order(k) return iterator to kth element. 0 indexed.
// X.order_of_key(k) returns count of elements strictly less than k.

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// template <class T>
// using ordered_set =  __gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
#define nl '\n'
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
 
using ll = long long int;
using pii = pair<ll,ll>;
using mii = map<ll,ll>;
using umii = unordered_map<ll,ll>;
using vi = vector<int>;
using vpii = vector<pii>;
using vvi = vector<vi>;
using vvii = vector<vpii>;

template<class T> bool chmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool chmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const ll INF = 1e18;
const ll N = 1e5+5;

// #define dbg(...)

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
class Solution {
public:

    void dfs(int x, int y, int n, int m, vvi& grid, vector<vector<bool>>& vis){
        if(x < 0 || x >= n || y < 0 || y >= m || vis[x][y] || !grid[x][y]){
            return;
        }
        vis[x][y] = 1;
        for(int i = 0; i < 4; i++){
            dfs(x + dx[i], y + dy[i], n, m, grid, vis);
        }
    }

    bool check(vvi& grid){
        int n = grid.size(), m = grid[0].size();
        vector<vector<bool>> vis(n, vector<bool> (m,0));
        int cnt = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(grid[i][j] == 1 && !vis[i][j]){
                    dfs(i,j,n,m,grid,vis);
                    cnt++;
                }
            }
        }
        dbg(grid, cnt);
        return cnt != 1;
    }

    int minDays(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        if(check(grid)){
            return 0;
        } 
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(grid[i][j] == 1){
                    grid[i][j] = 0;
                    if(check(grid)){
                        return 1;
                    }
                    grid[i][j] = 1;
                }
            }
        }       
        return 2;
    }
};
30620