---
id: 6a26df95efa55a2524399744
title: "Challenge 363: Bucket Fill 2"
challengeType: 29
dashedName: challenge-363
---

# --description--

Given a 2D grid of single-letter color strings and a target color, return the minimum number of flood fill "clicks" needed to make the entire grid the target color.

- Each click changes the clicked cell's color and the entire region of connected cells of the same color with the target color.
- Cells are connected horizontally and vertically (not diagonally).

# --hints--

`bucket_fill([["R", "R"], ["R", "R"]], "G")` should return `1`.

```js
({test: () => { runPython(`
from unittest import TestCase
TestCase().assertEqual(bucket_fill([["R", "R"], ["R", "R"]], "G"), 1)`)
}})
```

`bucket_fill([["B", "B", "B"], ["B", "B", "B"], ["B", "B", "B"]], "B")` should return `0`.

```js
({test: () => { runPython(`
from unittest import TestCase
TestCase().assertEqual(bucket_fill([["B", "B", "B"], ["B", "B", "B"], ["B", "B", "B"]], "B"), 0)`)
}})
```

`bucket_fill([["G", "Y", "Y"], ["G", "Y", "G"], ["Y", "Y", "G"]], "R")` should return `3`.

```js
({test: () => { runPython(`
from unittest import TestCase
TestCase().assertEqual(bucket_fill([["G", "Y", "Y"], ["G", "Y", "G"], ["Y", "Y", "G"]], "R"), 3)`)
}})
```

`bucket_fill([["G", "G", "P", "Y"], ["O", "P", "P", "P"], ["O", "O", "P", "G"], ["G", "O", "O", "G"]], "P")` should return `5`.

```js
({test: () => { runPython(`
from unittest import TestCase
TestCase().assertEqual(bucket_fill([["G", "G", "P", "Y"], ["O", "P", "P", "P"], ["O", "O", "P", "G"], ["G", "O", "O", "G"]], "P"), 5)`)
}})
```

`bucket_fill([["G", "G", "C", "C", "O"], ["B", "Y", "B", "Y", "O"], ["B", "J", "O", "J", "B"], ["G", "Y", "Y", "Y", "B"], ["G", "P", "P", "G", "G"]], "Y")` should return `12`.

```js
({test: () => { runPython(`
from unittest import TestCase
TestCase().assertEqual(bucket_fill([["G", "G", "C", "C", "O"], ["B", "Y", "B", "Y", "O"], ["B", "J", "O", "J", "B"], ["G", "Y", "Y", "Y", "B"], ["G", "P", "P", "G", "G"]], "Y"), 12)`)
}})
```

# --seed--

## --seed-contents--

```py
def bucket_fill(grid, target_color):

    return grid
```

# --solutions--

```py
def bucket_fill(grid, target_color):
    rows = len(grid)
    cols = len(grid[0])
    visited = set()

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

    clicks = 0
    for r in range(rows):
        for c in range(cols):
            if (r, c) not in visited and grid[r][c] != target_color:
                dfs(r, c, grid[r][c])
                clicks += 1

    return clicks
```
