План курса / Все задачи / Алгоритмы и структуры данных

Раскраска по номерам

легко

Дана раскраска по номерам в виде двумерного массива grid. Нужно определить минимальное количество заливок, необходимых, чтобы «закрасить» всю картину.

Когда мы делаем «заливку» (например, в графическом редакторе), мы выбираем клетку, и одновременно «заливаются» все соседние клетки того же цвета. Соседними считаем клетки сверху, снизу, слева и справа.

Пример 1:

Ввод: grid =
[[1,1,1,1,1,1,1,1]
,[1,2,2,1,1,2,2,1]
,[1,2,1,2,2,1,2,1]
,[1,2,2,2,2,2,2,1]
,[1,1,1,1,1,1,1,1]]
Вывод: 4

Ограничения:

len(grid) >= 1
len(grid[i]) >= 1

using System;
using System.Collections.Generic;

public class Solution
{
    // Проверяет, находятся ли индексы i и j в пределах матрицы
    private static bool InBound(int i, int j, List<List<int>> grid)
    {
        return 0 <= i && i < grid.Count && 0 <= j && j < grid[0].Count;
    }

    // Рекурсивный обход в глубину (DFS)
    private static void Dfs(int i, int j, int needsColor, List<List<bool>> used, List<List<int>> grid)
    {
        if (!InBound(i, j, grid) || needsColor != grid[i][j] || used[i][j])
        {
            return;
        }
        // Помечаем клетку как посещённую
        used[i][j] = true;
        // Используем массив для перебора соседних клеток
        int[][] nextSteps = new int[][]
        {
            new int[] { i, j + 1 },
            new int[] { i, j - 1 },
            new int[] { i + 1, j },
            new int[] { i - 1, j }
        };
        foreach (var nextStep in nextSteps)
        {
            Dfs(nextStep[0], nextStep[1], needsColor, used, grid);
        }
    }

    public static int Draw(List<List<int>> grid)
    {
        // Инициализация массива для отслеживания посещённых клеток
        List<List<bool>> used = new List<List<bool>>();
        foreach (var row in grid)
        {
            List<bool> usedRow = new List<bool>(new bool[row.Count]);
            used.Add(usedRow);
        }

        int result = 0;
        // Перебор всех клеток матрицы
        for (int i = 0; i < grid.Count; i++)
        {
            for (int j = 0; j < grid[i].Count; j++)
            {
                if (!used[i][j])
                {
                    Dfs(i, j, grid[i][j], used, grid);
                    result++;
                }
            }
        }

        return result;
    }
}

#include <vector>

using namespace std;

// Проверяет, находятся ли индексы i и j в пределах матрицы
bool inBound(int i, int j, const vector<vector<int>>& grid) {
    return 0 <= i && i < grid.size() && 0 <= j && j < grid[0].size();
}

// Рекурсивный обход в глубину (DFS)
void dfs(int i, int j, int needsColor, vector<vector<bool>>& used, const vector<vector<int>>& grid) {
    if (!inBound(i, j, grid) || needsColor != grid[i][j] || used[i][j]) {
        return;
    }
    // Помечаем клетку как посещённую
    used[i][j] = true;
    // Используем массив для перебора соседних клеток
    vector<vector<int>> nextSteps = {{i, j + 1}, {i, j - 1}, {i + 1, j}, {i - 1, j}};
    for (const auto& nextSteps : nextSteps) {
        dfs(nextSteps[0], nextSteps[1], needsColor, used, grid);
    }
}

int draw(const vector<vector<int>>& grid) {
    // Инициализация массива для отслеживания посещённых клеток
    vector<vector<bool>> used(grid.size(), vector<bool>(grid[0].size(), false));
    int result = 0;
    // Перебор всех клеток матрицы
    for (int i = 0; i < grid.size(); i++) {
        for (int j = 0; j < grid[i].size(); j++) {
            if (!used[i][j]) {
                dfs(i, j, grid[i][j], used, grid);
                result++;
            }
        }
    }
    return result;
}

package main

// Проверяет, находятся ли индексы i и j в пределах матрицы
func inBound(i, j int, grid [][]int) bool {
    return i >= 0 && i < len(grid) && j >= 0 && j < len(grid[0])
}

// Рекурсивный обход в глубину (DFS)
func dfs(i, j, needsColor int, used [][]bool, grid [][]int) {
    if !inBound(i, j, grid) || needsColor != grid[i][j] || used[i][j] {
        return
    }
    // Помечаем клетку как посещённую
    used[i][j] = true
    // Используем массив для перебора соседних клеток
    nextSteps := [][]int{
        {i, j + 1},
        {i, j - 1},
        {i + 1, j},
        {i - 1, j},
    }

    for _, nextStep := range nextSteps {
        dfs(nextStep[0], nextStep[1], needsColor, used, grid)
    }
}

func draw(grid [][]int) int {
    // Инициализация массива для отслеживания посещённых клеток
    used := make([][]bool, len(grid))
    for i := range used {
        used[i] = make([]bool, len(grid[0]))
    }
    result := 0
    // Перебор всех клеток матрицы
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[i]); j++ {
            if !used[i][j] {
                dfs(i, j, grid[i][j], used, grid)
                result++
            }
        }
    }
    return result
}

import java.util.*;

public class Solution {

    // Проверяет, находятся ли индексы i и j в пределах матрицы
    private static boolean inBound(int i, int j, List<List<Integer>> grid) {
        return 0 <= i && i < grid.size() && 0 <= j && j < grid.get(0).size();
    }

    // Рекурсивный обход в глубину (DFS)
    private static void dfs(int i, int j, int needsColor, List<List<Boolean>> used, List<List<Integer>> grid) {
        if (!inBound(i, j, grid) || needsColor != grid.get(i).get(j) || used.get(i).get(j)) {
            return;
        }
        // Помечаем клетку как посещённую
        used.get(i).set(j, true);
        // Используем массив для перебора соседних клеток
        int[][] nextSteps = {{i, j + 1}, {i, j - 1}, {i + 1, j}, {i - 1, j}};
        for (int[] nextStep : nextSteps) {
            dfs(nextStep[0], nextStep[1], needsColor, used, grid);
        }
    }

    // Основная функция для подсчёта областей с разными цветами
    public static int draw(List<List<Integer>> grid) {
        // Инициализация массива для отслеживания посещённых клеток
        List<List<Boolean>> used = new ArrayList<>();
        for (List<Integer> row : grid) {
            List<Boolean> usedRow = new ArrayList<>();
            for (int k = 0; k < row.size(); k++) {
                usedRow.add(false);
            }
            used.add(usedRow);
        }

        int result = 0;
        // Перебор всех клеток матрицы
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid.get(i).size(); j++) {
                if (!used.get(i).get(j)) {
                    dfs(i, j, grid.get(i).get(j), used, grid);
                    result++;
                }
            }
        }

        return result;
    }
}

from typing import *

# Проверяет, находятся ли индексы i и j в пределах матрицы
def in_bound(i: int, j: int, grid: List[List[int]]) -> bool:
    return 0 <= i < len(grid) and 0 <= j < len(grid[0])

# Рекурсивный обход в глубину (DFS)
def dfs(i: int, j: int, needs_color: int, used: List[List[bool]], grid: List[List[int]]) -> None:
    if not in_bound(i, j, grid) or needs_color != grid[i][j] or used[i][j]:
        return
    # Помечаем клетку как посещённую    
    used[i][j] = True
    # Используем массив для перебора соседних клеток
    next_steps = [[i, j+1], [i, j-1], [i+1, j], [i-1, j]]
    for next_step in next_steps:
        dfs(next_step[0], next_step[1], needs_color, used, grid)
    

def draw(grid: List[List[int]]) -> int:
    # Инициализация массива для отслеживания посещённых клеток
    used = [[False for _ in range(len(el))] for el in grid]
    result = 0
    # Перебор всех клеток матрицы
    for i in range(len(grid)):
        for j in range(len(grid[i])):
            if not used[i][j]:
                dfs(i, j, grid[i][j], used, grid)
                result += 1
    return result

// Проверяет, находятся ли индексы i и j в пределах матрицы
function inBound(i, j, grid) {
    return 0 <= i && i < grid.length && 0 <= j && j < grid[0].length;
}

// Рекурсивный обход в глубину (DFS)
function dfs(i, j, needsColor, used, grid) {
    if (!inBound(i, j, grid) || needsColor !== grid[i][j] || used[i][j]) {
        return;
    }
    // Помечаем клетку как посещённую
    used[i][j] = true;
    // Используем массив для перебора соседних клеток
    const nextSteps = [[i, j + 1], [i, j - 1], [i + 1, j], [i - 1, j]];
    for (const [nextI, nextJ] of nextSteps) {
        dfs(nextI, nextJ, needsColor, used, grid);
    }
}

export function draw(grid) {
    // Инициализация массива для отслеживания посещённых клеток
    const used = grid.map(row => row.map(() => false));
    let result = 0;

    // Перебор всех клеток матрицы
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            if (!used[i][j]) {
                dfs(i, j, grid[i][j], used, grid);
                result++;
            }
        }
    }

    return result;
}

Оценка сложности

Время: O(n * m), где n кол-во строк и m кол-во столбцов входного массива
Память: O(n * m), где n кол-во строк и m кол-во столбцов входного массива