You are given an m x n integer matrix grid, and three integers row, col, and color. Each value in the grid represents the color of the grid square at that location.

Two squares belong to the same connected component if they have the same color and are next to each other in any of the 4 directions.

The border of a connected component is all the squares in the connected component that are either 4-directionally adjacent to a square not in the component, or on the boundary of the grid (the first or last row or column).

You should color the border of the connected component that contains the square grid[row][col] with color.

Return the final grid.

&nbsp;
Example 1:
Input: grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
Output: [[3,3],[3,2]]
Example 2:
Input: grid = [[1,2,2],[2,3,2]], row = 0, col = 1, color = 3
Output: [[1,3,3],[2,3,3]]
Example 3:
Input: grid = [[1,1,1],[1,1,1],[1,1,1]], row = 1, col = 1, color = 2
Output: [[2,2,2],[2,1,2],[2,2,2]]

&nbsp;
Constraints:


	m == grid.length
	n == grid[i].length
	1 &lt;= m, n &lt;= 50
	1 &lt;= grid[i][j], color &lt;= 1000
	0 &lt;= row &lt; m
	0 &lt;= col &lt; n


class Solution:
    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:

        rows, cols = len(grid), len(grid[0])
        border_color = grid[row][col]
        border = []

        # Check if a node is a border node or not
        def is_border(r, c):
            if r == 0 or r == rows - 1 or c == 0 or c == cols - 1:
                return True

            for dr, dc in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                nr, nc = r + dr, c + dc
                if grid[nr][nc] != border_color:
                    return True
            return False

        def dfs(r, c):
            if r < 0 or c < 0 or r == rows or c == cols or (r, c) in visited or grid[r][c] != border_color:
                return
            visited.add((r, c))

            if is_border(r, c):
                border.append((r, c))

            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

        visited = set()
        dfs(row, col)
        for r, c in border:
            grid[r][c] = color
        return grid
class Solution {
    public int[][] colorBorder(int[][] grid, int row, int col, int color) {
    dfs(grid,row,col,grid[row][col]);
        for(int i = 0;i<grid.length;i++)
        {
            for(int j = 0;j<grid[0].length;j++)
            {
               if(grid[i][j]<0)
               {
                   grid[i][j] = color;
               }
            }
        }
     
        
        return grid;
    }
    int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
      public void dfs(int[][] grid, int row, int col, int color) {
        grid[row][col] = - color;
          int count = 0;
         for(int i = 0;i<4;i++)
         {
             int rowdash = row+dirs[i][0];
             int coldash = col+dirs[i][1];
             
             if(rowdash<0||coldash<0||rowdash>=grid.length||coldash>=grid[0].length||
               Math.abs(grid[rowdash][coldash])!=color)
             {
                 continue;
             }
             count++;
             
             if(grid[rowdash][coldash]==color)
             {
                 dfs(grid,rowdash,coldash,color);
             }
     
         }
          if(count==4)
          {
              grid[row][col] = color;
          }
      
    }
}
// marking element -ve and then fix it while backtracking worked as visited matrix
// marking element 1e9 and not fixing it while backtracking works for coloring element
class Solution {
private:
    int m,n;
public:
    bool is_valid(int i,int j,vector<vector<int>> &grid,int org_color){
        return i >= 0 and j >= 0 and i < m and j < n and grid[i][j] == org_color and grid[i][j] > 0;
    }

    bool is_colorable(int i,int j,vector<vector<int>> &grid,int org_color){
        if(i == 0 or j == 0 or i == m-1 or j == n-1) return true; // boundary condn

        // checking any of the neighbour is of opposite color or not
        if(i-1 >= 0 and abs(grid[i-1][j]) != org_color and grid[i-1][j] != 1e9) return true;

        if(i+1 < m and abs(grid[i+1][j]) != org_color and grid[i+1][j] != 1e9) return true;

        if(j-1 >= 0 and abs(grid[i][j-1]) != org_color and grid[i][j-1] != 1e9) return true;

        if(j+1 < n and abs(grid[i][j+1]) != org_color and grid[i][j+1] != 1e9) return true;

        return false;
    }

    void dfs(int i,int j,vector<vector<int>> &grid,int org_color){
        if(!is_valid(i,j,grid,org_color)) return;

        if(is_colorable(i,j,grid,org_color)) grid[i][j] = 1e9;
        else grid[i][j] = -grid[i][j];

        dfs(i-1,j,grid,org_color); dfs(i+1,j,grid,org_color); // up and down
        dfs(i,j-1,grid,org_color); dfs(i,j+1,grid,org_color); // left and right

        if(grid[i][j] < 0) grid[i][j] = -grid[i][j];
    }
    vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col, int color){
        m = grid.size(), n = grid[0].size();
        dfs(row,col,grid,grid[row][col]);
        for(auto &it : grid){
            for(auto &i : it){
                if(i == 1e9) i = color;
            }
        }
        return grid;
    }
};
var colorBorder = function(grid, row, col, color) {
    const m = grid.length;
    const n = grid[0].length;
    const dirs = [-1, 0, 1, 0, -1];

    const res = [];

    for (let i = 0; i < m; i++) {
        res[i] = new Array(n).fill(-1);
    }

    const val = grid[row][col];

    const stack = [];
    const visited = new Set();

    visited.add(`${row}#${col}`); 
    stack.push([row, col]);

    while (stack.length > 0) {
        const [currRow, currCol] = stack.pop();

        let isConnected = true;

        for (let i = 0; i < dirs.length - 1; i++) {
            const neiRow = currRow + dirs[i];
            const neiCol = currCol + dirs[i + 1];

            if (withinBound(neiRow, neiCol)) {
                if (!visited.has(`${neiRow}#${neiCol}`)) {
                    if (grid[neiRow][neiCol] === val) {
                        visited.add(`${neiRow}#${neiCol}`);
                        stack.push([neiRow, neiCol]);
                    }
                    else {
                        isConnected = false;
                    }
                }
            }
        }

        if (isBorder(currRow, currCol) || !isConnected) res[currRow][currCol] = color;
    }

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (res[i][j] === -1) {
                res[i][j] = grid[i][j];
            }
        }
    }

    return res;


    function withinBound(row, col) {
        return row >= 0 && col >= 0 && row < m && col < n;
    }

    function isBorder(row, col) {
        return row === 0 || col === 0 || row === m - 1 || col === n - 1;
    }
};
Coloring A Border