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

<p>Two squares are called <strong>adjacent</strong> if they are next to each other in any of the 4 directions.</p>

<p>Two squares belong to the same <strong>connected component</strong> if they have the same color and they are adjacent.</p>

<p>The <strong>border of a connected component</strong> is all the squares in the connected component that are either adjacent to (at least) a square not in the component, or on the boundary of the grid (the first or last row or column).</p>

<p>You should color the <strong>border</strong> of the <strong>connected component</strong> that contains the square <code>grid[row][col]</code> with <code>color</code>.</p>

<p>Return <em>the final grid</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
<strong>Output:</strong> [[3,3],[3,2]]
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> grid = [[1,2,2],[2,3,2]], row = 0, col = 1, color = 3
<strong>Output:</strong> [[1,3,3],[2,3,3]]
</pre><p><strong class="example">Example 3:</strong></p>
<pre><strong>Input:</strong> grid = [[1,1,1],[1,1,1],[1,1,1]], row = 1, col = 1, color = 2
<strong>Output:</strong> [[2,2,2],[2,1,2],[2,2,2]]
</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;= 50</code></li>
	<li><code>1 &lt;= grid[i][j], color &lt;= 1000</code></li>
	<li><code>0 &lt;= row &lt; m</code></li>
	<li><code>0 &lt;= col &lt; n</code></li>
</ul>

from typing import List

class Solution:
    def __init__(self):
        self.directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # Directions for right, down, left, and up
        self.rows = 0
        self.cols = 0
        self.visited = []  # To track visited cells
        self.borders = []  # To store border cells

    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:
        self.rows = len(grid)  # Get the number of rows
        self.cols = len(grid[0])  # Get the number of columns
        self.visited = [[False] * self.cols for _ in range(self.rows)]  # Initialize visited matrix
        self.borders = []  # Initialize borders list
        originalColor = grid[row][col]  # Get the color of the starting cell
        self.dfs(grid, row, col, originalColor)  # Perform DFS to find the connected component

        # Color the border cells with the new color
        for x, y in self.borders:
            grid[x][y] = color
        return grid  # Return the modified grid

    def dfs(self, grid: List[List[int]], x: int, y: int, color: int):
        self.visited[x][y] = True  # Mark the cell as visited
        isBorder = False  # Flag to check if the cell is a border cell
        for dx, dy in self.directions:  # Explore all four directions
            newX, newY = x + dx, y + dy  # Calculate new cell coordinates
            if newX < 0 or newX >= self.rows or newY < 0 or newY >= self.cols or grid[newX][newY] != color:
                isBorder = True  # Mark as border if out of bounds or different color
            elif not self.visited[newX][newY]:
                self.dfs(grid, newX, newY, color)  # Continue DFS if the cell is unvisited and same color
        if isBorder:
            self.borders.append((x, y))  # Add border cell to the list
16800