wehub-resource-sync
dde272c4b8
i18n - Build Validation / Validate i18n Builds (24) (push) Has been cancelled
CI - Node.js / Lint (24) (push) Has been cancelled
CI - Node.js / Build (24) (push) Has been cancelled
CI - Node.js / Test (24) (push) Has been cancelled
CI - Node.js / Test - Upcoming Changes (24) (push) Has been cancelled
CI - Node.js / Test - i18n (italian, 24) (push) Has been cancelled
CI - Node.js / Test - i18n (portuguese, 24) (push) Has been cancelled
CD - Docker - GHCR Images / Build and Push Images (push) Has been cancelled
102 lines
2.8 KiB
Markdown
102 lines
2.8 KiB
Markdown
---
|
|
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
|
|
```
|