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

id, title, challengeType, dashedName

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

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

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

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.

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.

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.

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.

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--

function bucketFill(grid, targetColor) {

  return grid;
}

--solutions--

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]);
        }
      }
    }
  }
}