freecodecamp--freecodecamp/curriculum/challenges/english/blocks/daily-coding-challenges-python/6a26df95efa55a2524399746.md

id, title, challengeType, dashedName

id	title	challengeType	dashedName
6a26df95efa55a2524399746	Challenge 365: The Last Challenge: Bucket Fill 3	29	challenge-365

--description--

Today marks a year of daily coding challenges. This is the last new one for now. Good luck!

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 that color.

• Each click changes the clicked cell's color and the entire region of connected cells of the same color (4-directional).
• Clicks can use any color as an intermediate step, not just the target color.

--hints--

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

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

bucket_fill([["G", "G", "G"], ["G", "G", "G"], ["G", "G", "G"]], "G") should return 0.

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

bucket_fill([["P", "P", "Y"], ["Y", "P", "Y"], ["Y", "P", "P"]], "O") should return 2.

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

bucket_fill([["G", "Y", "C", "C"], ["Y", "Y", "Y", "B"], ["C", "Y", "B", "B"], ["C", "B", "B", "C"]], "R") should return 4.

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

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

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

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

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

--seed--

--seed-contents--

def bucket_fill(grid, target_color):

    return grid

--solutions--

def bucket_fill(grid, target_color):
    from collections import deque

    rows = len(grid)
    cols = len(grid[0])

    def grid_key(g):
        return tuple(tuple(r) for r in g)

    def get_region(g, row, col):
        color = g[row][col]
        visited = set()
        stack = [(row, col)]
        while stack:
            r, c = stack.pop()
            if (r, c) in visited or not (0 <= r < rows and 0 <= c < cols) or g[r][c] != color:
                continue
            visited.add((r, c))
            stack.extend([(r+1,c),(r-1,c),(r,c+1),(r,c-1)])
        return visited

    def flood_fill(g, row, col, color):
        next_g = [list(r) for r in g]
        for r, c in get_region(g, row, col):
            next_g[r][c] = color
        return next_g

    def is_complete(g):
        return all(cell == target_color for row in g for cell in row)

    initial = [list(r) for r in grid]
    if is_complete(initial):
        return 0

    queue = deque([(initial, 0)])
    seen = {grid_key(initial)}

    while queue:
        current, clicks = queue.popleft()
        all_colors = set(cell for row in current for cell in row) | {target_color}

        visited_all = set()
        region_roots = []
        for r in range(rows):
            for c in range(cols):
                if (r, c) not in visited_all:
                    region = get_region(current, r, c)
                    visited_all |= region
                    region_roots.append((r, c))

        for r, c in region_roots:
            for color in all_colors:
                if color == current[r][c]:
                    continue
                next_g = flood_fill(current, r, c, color)
                if is_complete(next_g):
                    return clicks + 1
                key = grid_key(next_g)
                if key not in seen:
                    seen.add(key)
                    queue.append((next_g, clicks + 1))