---
id: 6a26df95efa55a2524399746
title: "Challenge 365: The Last Challenge: Bucket Fill 3"
challengeType: 28
dashedName: 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--

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

```js
assert.equal(bucketFill([["B", "B"], ["B", "B"]], "R"), 1);
```

`bucketFill([["G", "G", "G"], ["G", "G", "G"], ["G", "G", "G"]], "G")` should return `0`.

```js
assert.equal(bucketFill([["G", "G", "G"], ["G", "G", "G"], ["G", "G", "G"]], "G"), 0);
```

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

```js
assert.equal(bucketFill([["P", "P", "Y"], ["Y", "P", "Y"], ["Y", "P", "P"]], "O"), 2);
```

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

```js
assert.equal(bucketFill([["G", "Y", "C", "C"], ["Y", "Y", "Y", "B"], ["C", "Y", "B", "B"], ["C", "B", "B", "C"]], "R"), 4);
```

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

```js
assert.equal(bucketFill([["G", "G", "O", "O"], ["G", "Y", "B", "Y"], ["B", "Y", "B", "Y"], ["B", "Y", "B", "Y"], ["G", "G", "G", "G"]], "P"), 5);
```

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

```js
assert.equal(bucketFill([["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--

```js
function bucketFill(grid, targetColor) {

  return grid;
}
```

# --solutions--

```js
function bucketFill(grid, targetColor) {
  const rows = grid.length;
  const cols = grid[0].length;

  function gridToString(g) {
    return g.map(r => r.join(",")).join("|");
  }

  function getRegion(g, row, col) {
    const color = g[row][col];
    const visited = new Set();
    const stack = [[row, col]];
    while (stack.length) {
      const [r, c] = stack.pop();
      const key = `${r},${c}`;
      if (visited.has(key)) continue;
      if (r < 0 || r >= rows || c < 0 || c >= cols) continue;
      if (g[r][c] !== color) continue;
      visited.add(key);
      stack.push([r+1,c],[r-1,c],[r,c+1],[r,c-1]);
    }
    return visited;
  }

  function floodFill(g, row, col, color) {
    const next = g.map(r => [...r]);
    const region = getRegion(g, row, col);
    for (const key of region) {
      const [r, c] = key.split(",").map(Number);
      next[r][c] = color;
    }
    return next;
  }

  function isComplete(g) {
    return g.every(row => row.every(cell => cell === targetColor));
  }

  function getColors(g) {
    return [...new Set([...g.flat(), targetColor])];
  }

  function getRegionRoots(g) {
    const visited = new Set();
    const roots = [];
    for (let r = 0; r < rows; r++) {
      for (let c = 0; c < cols; c++) {
        const key = `${r},${c}`;
        if (!visited.has(key)) {
          const region = getRegion(g, r, c);
          for (const k of region) visited.add(k);
          roots.push([r, c]);
        }
      }
    }
    return roots;
  }

  const initial = grid.map(r => [...r]);
  if (isComplete(initial)) return 0;

  const queue = [[initial, 0]];
  const seen = new Set([gridToString(initial)]);

  while (queue.length) {
    const [current, clicks] = queue.shift();
    const colors = getColors(current);
    const roots = getRegionRoots(current);

    for (const [r, c] of roots) {
      for (const color of colors) {
        if (color === current[r][c]) continue;
        const next = floodFill(current, r, c, color);
        if (isComplete(next)) return clicks + 1;
        const key = gridToString(next);
        if (!seen.has(key)) {
          seen.add(key);
          queue.push([next, clicks + 1]);
        }
      }
    }
  }
}
```
