Меню
Главная

Статистика

 

 


Пример #2.

В таблице c N строками и M столбцами, состоящей из 0 и 1, необходимо найти квадратный блок максимального размера, состоящий из одних единиц. Под блоком понимается множество элементов соседних (подряд идущих) строк и столбцов таблицы. Интересующая нас часть показана на рис. 1.

1 1 1 1 1 1
0 1 1 1 0 1
1 1 1 1 1 1
1 1 0 1 1 1
1 0 1 1 0 1
Рис. 1.

Положение любого квадратного блока может быть определено его размером и положением одного из его углов.

Пусть T(i, j) есть функция, значение которой соответствует размеру максимального квадратного блока, состоящего из одних единиц, правый нижний угол которого расположен в позиции (i, j). Функция T(i, j) вычисляет элемент таблицы B[i, j]. Для примера на рис. значения T(i, j) будут иметь вид

i\j 1 2 3 4 5 6
1 1 1 1 1 1 1
2 0 1 2 2 0 1
3 1 1 2 3 1 1
4 1 2 0 1 2 2
5 1 0 1 1 0 1

Таким образом, наша задача свелась к вычислению максимального значения функции Т при всевозможных значениях параметров i и j. Этой функции может быть поставлена в соответствие таблица размера N*M.

Определим сначала значения элементов таблицы В, расположенных в первой строке и в первом столбце. Получим:
В(1, 1) = А[1, 1],
В(1, j) = А[1, j] при j³2,
В(i, 1) = A[i, 1] при i³2.

Эти соотношения следуют из того факта, что в этих случаях рассматриваемая область матрицы А содержит только один элемент матрицы.

При 2£i£N и 2£j£M для этой функции можно записать следующие рекуррентные соотношения:
B[i, j] = 0, если A[i, j] = 0 и
B[i, j] = min{B[i - 1, j], B[i, j - 1], B[i - 1, j - 1]} + 1, если A[i, j] = 1

Первое соотношение показывает, что размер максимального единичного блока с правым нижним углом в позиции (i, j) равен нулю в случае A[i, j] = 0.

Убедимся в правильности второго соотношения. Действительно, величина B[i - 1, j] соответствует максимальному размеру единичного блока таблицы A с правым нижним углом в позиции (i - 1, j). Тогда размер единичного блока с правым нижним углом в позиции (i, j) не превышает величину B[i - 1, j] + 1, так как к блоку в позиции (i - 1, j) могла добавиться только одна строка. Величина B[i, j - 1] соответствует максимальному размеру единичного блока таблицы A с правым нижним углом в позиции (i, j - 1). Тогда размер единичного блока с правым нижним углом в позиции (i, j) не превышает величину B[i, j - 1] + 1, так как к блоку в позиции (i - 1, j) мог добавиться только один столбец. Величина B[i - 1, j - 1] соответствует максимальному размеру единичного блока таблицы A с правым нижним углом в позиции (i - 1, j - 1). Тогда размер единичного блока с правым нижним углом в позиции (i, j) не превышает величину B[i - 1, j - 1] + 1, так как к блоку в позиции (i - 1, j - 1) могли добавиться только одна строка и один столбец. Итак, размер единичного блока с правым нижним углом в позиции (i, j) равен min{B[i - 1, j], B[i, j - 1], B[i - 1, j - 1]} + 1. 

В[1, 1]: = A[1, 1];
For  j:=2 to 6 do
 В[1, j]: = A[1, j];
for i:= 2 to 5 do
 В[i, 1]: = A[i, 1];
for i:=2 to  5 do
   for j:=2 to 6 do
      if A[i, j]: = 1 then
       begin
          B[i, j]: = min(B[i, j - 1], B[i - 1, j]);
           B[i, j]: = min(B[i, j], B[i - 1, j - 1]) + 1
       end
     else
           B[i, j]: = 0;


Задача #1. Минимальный штраф - 1
Имя входного файла input.txt
Имя выходного файла output.txt
Максимальное время работы на одном тесте 2 секунды

Задана матрица натуральных чисел A[1..N, 1..M], m<=n. За каждый проход tчерез клетку (i, j) взимается штраф A[i, j]. Необходимо определить путь с минимальным суммарным штрафом, с которым можно пройти из клетки (1, 1) в клетку (n, m). При этом из текущей клетки можно переходить в любую из 3-х соседних клеток, стоящих в строке с номером, на 1 большим текущего номера строки.

Формат входных данных

Первая строка входного файла содержит числа N и M (1<=N, M<=100). Следующие строки входного файла содержат N*M натуральных чисел A[i, j] (1<=A[i, j]<=100).

Формат выходных данных

В первой строке выходного файла должен быть записан минимальный штраф. В каждой из следущих N строк должны быть записаны два по числа xi, yi -- i-ая клетка искомого пути.

Пример входного файла Пример выходного файла
3 2
2 1 3 4 2 3
 
8
1 1
2 1
3 2

Задача #2. Минимальный штраф - 2
Имя входного файла input.txt
Имя выходного файла output.txt
Максимальное время работы на одном тесте 2 секунды

Задана матрица натуральных чисел A[1..N, 1..M]. За каждый проход через клетку (i, j) взимается штраф A[i, j]. Необходимо определить путь с минимальным суммарным штрафом, с которым можно пройти из некотрой клетки первой строки в некоторую клетку N-ой строки. При этом из текущей клетки можно переходить в любую из 3-х соседних клеток, стоящих в строке с номером, на 1 большим текущего номера строки.

Формат входных данных

Первая строка входного файла содержит числа N и M (1<=N, M<=100). Далее идет N*M натуральных чисел A[i, j] (1<=A[i, j]<=100)

Формат выходных данных

Первая строка выходного файла должна содержать штраф. В каждой из следующих N строк должны быть записаны два числа xi, yi -- i-ая клетка искомого пути.

Пример входного файла Пример выходного файла
3 2
2 1 3 4 2 3
 
6
1 2
2 1
3 1

Назад