<p>Given an <code>m x n</code> 2D binary grid <code>grid</code> which represents a map of <code>&#39;1&#39;</code>s (land) and <code>&#39;0&#39;</code>s (water), return <em>the number of islands</em>.</p>

<p>An <strong>island</strong> is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> grid = [
  [&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;0&quot;],
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;],
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;0&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;]
]
<strong>Output:</strong> 1
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> grid = [
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;0&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;0&quot;,&quot;0&quot;,&quot;0&quot;,&quot;1&quot;,&quot;1&quot;]
]
<strong>Output:</strong> 3
</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;= 300</code></li>
	<li><code>grid[i][j]</code> is <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
</ul>

class Solution {
public:
    void func(vector<vector<char>>& grid, list<pair<int,int>>& que, int i, int j) {
        int n = grid.size(); int m = grid[0].size();
        pair<int,int> p = make_pair(i,j);
        que.push_back(p);
        grid[i][j] = '0';
        while(!que.empty()) {
            pair<int,int> ind = que.front();
            int r = ind.first, c = ind.second;
            que.pop_front();

            if(0 <= r+1 && r+1 < n && 0 <= c && c < m && grid[r+1][c] == '1') {
                p.first = r+1; p.second = c;
                que.push_back(p);
                grid[r+1][c] = '0';
            }
            if(0 <= r-1 && r-1 < n && 0 <= c && c < m && grid[r-1][c] == '1') {
                p.first = r-1; p.second = c;
                que.push_back(p);
                grid[r-1][c] = '0';
            }
            if(0 <= r && r < n && 0 <= c+1 && c+1 < m && grid[r][c+1] == '1') {
                p.first = r; p.second = c+1;
                que.push_back(p);
                grid[r][c+1] = '0';
            }
            if(0 <= r && r < n && 0 <= c-1 && c-1 < m && grid[r][c-1] == '1') {
                p.first = r; p.second = c-1;
                que.push_back(p);
                grid[r][c-1] = '0';
            }
        }
    }

    int numIslands(vector<vector<char>>& grid) {
        int n = grid.size(); int m = grid[0].size();
        list<pair<int,int>> que;
        int islands = 0;

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(grid[i][j] == '1') {
                    islands++;
                    func(grid, que, i, j);
                }
            }
        }

        return islands;
    }
};
























// class Solution:
// def numIslands(self, grid: List [List[str]l) →> int:
// islands = 0
// rows, cols = len(grid), len(grid [0])
// 口
// def bfs(r, c):
// q = deque()
// q-append ( (r, c))
// grid[r] [c] = '0'
// while q:
// row, col = q-popleft()
// directions = [[1,01, [-1,0], [0,1], [0,-1]]
// for dr, de in directions:
// r, c = row + dr, col + dc
// if 0 r < rows and 0 = c < cols and grid[r][c] =
// "1":
// q-append ((r, c))
// grid[r] [c] = '0'
// for r in range(rows):
// for c in range(cols):
// if grid[r][c] = "1":
// islands += 1
// bfs(r, c)
// return
// islands
20581