Групповая выборка свободных мест в кинотеатре методом пр…

//  ГРУППОВАЯ  ВЫБОРКА  СВОБОДНЫХ  МЕСТ  В  КИНОТЕАТРЕ  МЕТОДОМ  ПРОВЕШИВАНИЯ

/*

В кинотеатре n рядов по m мест в каждом (n и m не превосходят 20).
В двумерном массиве хранится информация о проданных билетах, число 1 означает, что билет на данное место уже продан, число 0 означает, что место свободно.
Поступил запрос на продажу k билетов на соседние места в одном ряду.
Определите, можно ли выполнить такой запрос.

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

Программа получает на вход числа n и m.
Далее идет n строк, содержащих m чисел (0 или 1), разделенных пробелами.
Затем дано число k.

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

Программа должна вывести номер ряда, в котором есть k подряд идущих свободных мест.
Если таких рядов несколько, то выведите номер наименьшего подходящего ряда.
Если подходящего ряда нет, выведите число 0.

*/


// РЕШЕНИЕ МЕТОДОМ ПРОВЕШИВАНИЯ

#include <iostream>
#include <vector>
using namespace std;

const int DIM = 21; // ограничитель размеров массива — не более 20 по 20

int main ()
{
    int i, j, k, m, n;

// ВВОД РАЗМЕРОВ МАССИВА
    cin >> n >> m;

    if (n > 0 && n < DIM && m > 0 && m < DIM) // проверка границ массива
        {
            vector <vector <bool>> tic (n);
            for (i = 0; i < n; i++) // заполнение массива
                {
                    tic[i].resize (m);
                    for (j = 0; j < m; j++)
                        {
                            cin >> k; // 0 либо 1?
                            tic[i][j] = (bool)k; // чистая формальность
                        }
                }

            cin >> k; // собственно размер запроса

            if (k <= m)   // если k > m, то заказ неисполним!
                {
                    const int dif = m - k; // кол–во вариантов выбора k мест подряд в ряду из m мест
                    for (i = 0; i < n; i++) // цикл по всем рядам…
                        {
                            j = 0;
                            while (j <= dif) // поиск внутри ряда…
                                {
                                    bool Hit = true;
                                    for (int jk = j + k; (j < jk) && Hit; j++) // попытка провешивания…
                                        {
                                            Hit = !(tic[i][j]); // условие успешного провешивания
                                        }
                                    if (Hit)
                                        {
                                            cout << (++i); // номер ряда на 1 больше индекса!
                                            return 0; // преждевременный выход из программы в случае успеха
                                        }
                                }
                        }
                }
        }
    cout << 0; // сюда попадаем в случае неудачи по всем рядам
    return 0;
}

/*
       _ПОЯСНЕНИЕ_

 •  ПРОВЕШИВАНИЕ — измерение расстояний на местности при помощи ВЕХИ — шеста заранее известной длины.
✓ В данной программе «веха» — конечная непрерывная выборка (последовательность) зрительских мест, число которых определяется заказом. Провешивание осуществляется формированием вехи и последующей проверкой состояния каждого из мест в пределах выбранной вехи.


       _ПОДСКАЗКА_

   ✓ Непрерывную выборку из Κ мест в ряду, в котором всего Μ мест, при условии, что Κ ≤ Μ, можно сделать Μ – Κ + 1 способом. Это и есть максимальное число провешиваний в пределах одного ряда.


Например:
•  при Κ == Μ решение единственное — занять все места в ряду,
•  при Κ == Μ – 1 решений 2: Κ мест в начале ряда или Κ мест в конце ряда,
•  при Κ == Μ – 2 вариантов 3: в начале, в конце или точно посередине.
*/