<p>An image is represented by an <code>m x n</code> integer grid <code>image</code> where <code>image[i][j]</code> represents the pixel value of the image.</p>

<p>You are also given three integers <code>sr</code>, <code>sc</code>, and <code>color</code>. You should perform a <strong>flood fill</strong> on the image starting from the pixel <code>image[sr][sc]</code>.</p>

<p>To perform a <strong>flood fill</strong>, consider the starting pixel, plus any pixels connected <strong>4-directionally</strong> to the starting pixel of the same color as the starting pixel, plus any pixels connected <strong>4-directionally</strong> to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with <code>color</code>.</p>

<p>Return <em>the modified image after performing the flood fill</em>.</p>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2</span></p>

<p><strong>Output:</strong> <span class="example-io">[[2,2,2],[2,2,0],[2,0,1]]</span></p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2021/06/01/flood1-grid.jpg" style="width: 613px; height: 253px;" /></p>

<p>From the center of the image with position <code>(sr, sc) = (1, 1)</code> (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) are colored with the new color.</p>

<p>Note the bottom corner is <strong>not</strong> colored 2, because it is not 4-directionally connected to the starting pixel.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0</span></p>

<p><strong>Output:</strong> <span class="example-io">[[0,0,0],[0,0,0]]</span></p>

<p><strong>Explanation:</strong></p>

<p>The starting pixel is already colored with 0, which is the same as the target color. Therefore, no changes are made to the image.</p>
</div>

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

<ul>
	<li><code>m == image.length</code></li>
	<li><code>n == image[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 50</code></li>
	<li><code>0 &lt;= image[i][j], color &lt; 2<sup>16</sup></code></li>
	<li><code>0 &lt;= sr &lt; m</code></li>
	<li><code>0 &lt;= sc &lt; n</code></li>
</ul>

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        int delr[4]={0,1,-1,0};
        int delc[4]={-1,0,0,1};
        int n=image.size();
        int m=image[0].size();
        vector<vector<int>> ans= image;
        int original_color=image[sr][sc];

        queue<pair<int,int>> q;
        q.push({sr,sc});
        ans[sr][sc]=color;

        while(!q.empty())
        {
            auto node=q.front();
            int row=node.first;
            int col=node.second;
            q.pop();

            for(int i=0;i<4;i++)
            {
                int nrow= row+ delr[i];
                int ncol= col+ delc[i];
                if(nrow>=0 and nrow<n and ncol>=0 and ncol<m and image[nrow][ncol]==original_color and ans[nrow][ncol]!=color)
                {
                    ans[nrow][ncol]=color;
                    q.push({nrow, ncol});
                }
            }
        }
        return ans;
    }
};


// class Solution {
//     private:
//     void dfs(int row,int col,vector<vector<int>>& ans, vector<vector<int>>& image, int newcolor,int inicolor)
//     {
//         ans[row][col]=newcolor;
//         int delrow[4]={0,1,-1,0};
//         int delcol[4]={-1,0,0,1};
//         int n=image.size();
//         int m=image[0].size();
//         for(int i=0;i<4;i++)
//         {
//             int nrow=row+delrow[i];
//             int ncol=col+delcol[i];
//             if(nrow>=0 and nrow<n and ncol>=0 and ncol<m and image[nrow][ncol]==inicolor and ans[nrow][ncol]!=newcolor)
//             {
//                 dfs(nrow,ncol,ans,image,newcolor,inicolor);
//             }
//         }
//     }
// public:
//     vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
//         int inicolor=image[sr][sc];
//         vector<vector<int>> ans= image;
//         dfs(sr,sc,ans,image,color,inicolor);
//         return ans;
//     }
// };
17000