<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 bfs(vector<vector<char>>&grid, int row, int col)
    {
     queue<pair<char,pair<int,int>>>q;
     char current=grid[row][col];
     grid[row][col]='0';
     q.push({current, {row,col}});
     //map to store visited
     map<pair<int,int>,bool>visited;
    while(!q.empty())
     {
       
          auto front=q.front();
          q.pop();
          int row=front.second.first;
          int col=front.second.second;

          //now we need to check for 4 directions 
          //checking for up
          int newrow=row-1;
          int newcol=col+0;
          //now check if it is in bounds
          if(newrow>=0 && newrow<grid.size() && newcol>=0 && newcol<grid[0].size() && grid[newrow][newcol]=='1' &&!visited[{newrow,newcol}])
          {
            //push and mark as visited
            q.push({grid[newrow][newcol],{newrow,newcol}});
           visited[{newrow,newcol}]=true;
            //also turn this to 0 so we don't need to do BFS on this now again
             grid[newrow][newcol]='0';

          }

          //checking for down
          newrow=row+1;
          newcol=col+0;
           if(newrow>=0 && newrow<grid.size() && newcol>=0 && newcol<grid[0].size() && grid[newrow][newcol]=='1' &&!visited[{newrow,newcol}])
          {
            //push and mark as visited
            q.push({grid[newrow][newcol],{newrow,newcol}});
            visited[{newrow,newcol}]=true;
            //also turn this to 0 so we don't need to do BFS on this now again
             grid[newrow][newcol]='0';

          }

          //checking for right
            newrow=row+0;
          newcol=col+1;
           if(newrow>=0 && newrow<grid.size()&& newcol>=0 && newcol<grid[0].size() && grid[newrow][newcol]=='1' &&!visited[{newrow,newcol}])
          {
            //push and mark as visited
            q.push({grid[newrow][newcol],{newrow,newcol}});
          visited[{newrow,newcol}]=true;
            //also turn this to 0 so we don't need to do BFS on this now again
             grid[newrow][newcol]='0';

          }

          //checking for left
          newrow=row+0;
          newcol=col-1;
           if(newrow>=0 && newrow<grid.size() && newcol>=0 && newcol<grid[0].size() && grid[newrow][newcol]=='1' &&!visited[{newrow,newcol}])
          {
            //push and mark as visited
            q.push({grid[newrow][newcol],{newrow,newcol}});
            visited[{newrow,newcol}]=true;
            //also turn this to 0 so we don't need to do BFS on this now again
             grid[newrow][newcol]='0';

     }

    }
    }
    int numIslands(vector<vector<char>>& grid)
    {
        int rows=grid.size();
        int column=grid[0].size();
        int numberofislands=0; 
        //the logic is we will call bfs for 1 and we will find all group of 1's thats connected and 
        //surrounded by 0, we will also convert them to 0's so they don't come again in out count 
        for(int i=0;i<rows;i++)
        {
            for(int j=0;j<column;j++)
             {
                if(grid[i][j]=='1')
                {
                    numberofislands+=1;
                    bfs(grid,i,j); 
                }
                    
             }
        }
        return numberofislands;
    }
};
28925