Форум программистов, компьютерный форум, киберфорум
PascalABC.NET
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
0 / 0 / 0
Регистрация: 03.02.2016
Сообщений: 1

Найти минимальное количество заливок, требуемых для стирания данной картинки

03.02.2016, 22:00. Показов 1330. Ответов 1
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
В окне редактора картинка отображается как прямоугольная таблица M × N клеток; каждая покрашена либо в чёрный, либо в белый цвет. Две клетки назовём соседними, если у них имеется общая сторона. Областью же будем называть максимальное подмножество клеток одного цвета, такое, что из каждой можно попасть в каждую, перемещаясь только по соседним клеткам этой области.

Заливка работает следующим образом: пользователь указывает на произвольную клетку таблицы, после чего вся область, содержащая данную клетку, перекрашивается в противоположный цвет.

Теперь Вася хочет научиться стирать изображения с помощью своего редактора. Картинка считается чистой, если она либо полностью чёрная, либо полностью белая. Определите минимальное число заливок, которое потребуется для того, чтобы сделать из данного изображения чистое.

Формат входных данных
Вводятся два натуральных числа N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 100) — количество строк и столбцов у таблицы, соответствующей данному изображению. В следующих N строках содержатся по M символов. В i‑й строке и j-м столбце стоит 0, если соответствующая клетка белая, и 1, если чёрная.

Формат выходных данных
Выведите одно число — минимальное количество заливок, требуемых для стирания данной картинки.

Пример
Входные данные
3 5

10101

01010

10101

Выходные данные
3
0
Лучшие ответы (1)
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
03.02.2016, 22:00
Ответы с готовыми решениями:

Найти минимальное количество монет для выдачи сдачи
Пожалуйста, помогите найти ошибку! Программа ищет минимальное кол-во монет, для выдачи сдачи. У меня в Dev C++ выдает очень большие числа....

Найти минимальное количество купюр для оплаты суммы
Я саму программу написал, да вот во время выполнения, в консоли, после ввода мною переменной summa, вообще ничего не происходит. Консоль...

Найти минимальное количество цветов m, необходимых для раскраски карты
Помогите,пожалуйста,решить задачу методом полного перебора. 1.На карте представлены n стран n<30 . В памяти компьютера карта...

1
 Аватар для JuriiMW
5095 / 2661 / 2355
Регистрация: 10.12.2014
Сообщений: 10,060
04.02.2016, 10:19
Лучший ответ Сообщение было отмечено gotowin как решение

Решение

Вот так:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
function OneColor(A : array [,] of Integer) : Boolean;
begin
  Result := False;
  for var Row := 0 to A.GetLength(0)-1 do
    for var Col := 0 to A.GetLength(1)-2 do
      if A[Row, Col] <> A[Row, Col+1] then
        Exit;
  for var Row := 0 to A.GetLength(0)-2 do
    for var Col := 0 to A.GetLength(1)-1 do
      if A[Row, Col] <> A[Row+1, Col] then
        Exit;
  Result := True;
end;
 
function FillCount(A : array [,] of Integer; R, C : Integer) : Integer;
  var U : array [,] of Integer;
 
  procedure Fill(Row, Col, fromColor, toColor : Integer);
  begin
    U[Row, Col] := toColor;
    
    if Row > 0 then
      if U[Row-1, Col] = fromColor then
        Fill(Row-1, Col, fromColor, toColor);
    
    if Row < U.GetLength(0)-1 then
      if U[Row+1, Col] = fromColor then
        Fill(Row+1, Col, fromColor, toColor);
 
    if Col > 0 then
      if U[Row, Col-1] = fromColor then
        Fill(Row, Col-1, fromColor, toColor);
    
    if Col < U.GetLength(1)-1 then
      if U[Row, Col+1] = fromColor then
        Fill(Row, Col+1, fromColor, toColor);
  end;
  
begin
  SetLength(U, A.GetLength(0), A.GetLength(1));
  for var Row := 0 to A.GetLength(0)-1 do
    for var Col := 0 to A.GetLength(1)-1 do
      U[Row, Col] := A[Row, Col];
  
  Result := 0;
  while Not OneColor(U) do
    begin
      Result += 1;
      Fill(R, C, U[R, C], (U[R, C] + 1) mod 2);
    end;
end;
 
begin
  var Rows := 3;
  var Cols := 5;
  var A : array [,] of Integer := ((1,0,1,0,1),(0,1,0,1,0),(1,0,1,0,1));
  
  var minFillCount := Rows * Cols;
  for var Row := 0 to Rows-1 do
    for var Col := 0 to Cols-1 do
      minFillCount := min(minFillCount, FillCount(A, Row, Col));
      
  WriteLn(minFillCount);
end.
Только нужно входные/выходные данные переделать на… Из вопроса не понятно от куда они берутся!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
04.02.2016, 10:19
Помогаю со студенческими работами здесь

Найти минимальное количество операций, необходимое для возведения k в степень n
Кто-нибудь, перепишете на с++ пожалуйста var N, i, k, count, m: byte; begin write('Введите степень: N = '); ...

Найти минимальное значение во втором столбце данной матрицы
дана целочисленная матрица размера 4 на 4.найти минимальное значение во втором столбце данной матрицы.Напишите программу и блок схему ......

Найти минимальное значение в первой строке данной матрицы
Дана действительная матрица размера 3x4. Найти минимальное значение в первой строке данной матрицы.

Найти и вывести на экран минимальное количество прыжков кенгуру для попадания в точку
Суперкенгуру может прыгать по прямой вправо и влево . Длина его первого прыжка составляет 1 м, второго — 2 м, третьего — 4 м и так далее...

Найти и вывести на экран минимальное количество прыжков для попадания в точку на расстоянии
3) Кенгуру умеет прыгать по прямой вправо и влево. Длина его первого прыжка - 1 метр, второго - 2, третьего - 4 и т.д. (длина каждого...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Новые блоги и статьи
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++
8Observer8 10.03.2026
Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE
8Observer8 10.03.2026
Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование
8Observer8 05.03.2026
Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D
8Observer8 04.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий
8Observer8 02.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru