/KIS-Admission

👨‍💻 Задача по выбранному направлению в рамках отбора на кафедру КИС МФТИ

Primary LanguageC++

Описание задачи [A004]

Требуется реализовать алгоритм поиска изображения, заданного числами от 0 до 255, внутри другого изображения. По условию, первая картинка - полная, а вторая - меньшего размера.

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

Пример:

0 1 2
3 4 5
6 7 8
0 1
3 4

Ответ: 0 0 или Northwest

Описание решения

В качестве тривиального решения поиска точного расположения картины можно рассмотреть простой проход по большей картине с проверкой в каждой позиции, начинается ли в ней вторая картина. Такое решение имеет сложность O((nm)^2), где n и m - размеры большей картины.

Для указания направления расположения картины в таком случае достаточно пройтись только по краям картины и сложность будет O((n+m)nm).

На ум приходит более оптимальное решение, поскольку в задаче происходит поиск подстроки в строке. Для этого можно воспользоваться алгоритмом КМП, который будет работать за время O(m). Опишем в таком случае итоговое решение:

За O(m) найдем все вхождения первой строки маленького изображения в первую строку большого, и сохраним их в массив. Повторим тоже самое со вторыми строками изображений и так далее, поддерживая пересечение получившихся массивов (это можно выполнить за линейное время, поэтому на сложность это не повлияет). Пока пересечение не пусто, переходим к следующей строке. Если мы дошли до последней строки меньшей картины, то ее вхождение найдено. В противном случае последовательно проделаем всю описанную работу, начиная проверки с остальных строк большей картины.

В результате сложность улучшится на порядок и будет O((n^2)m). В зависимости от соотношения для размеров картины, можно идти не по строкам, а по столбцам, тогда сложнось будет O(n(m^2)), либо можно просто транспонировать картину-матрицу за O(nm), что не повлияет на сложность.

В сорцах присутствует алгоритм Кнута-Морриса-Пратта, который несложно итегрировать в соответствии с описанием решения в его тривиальный вариант, но я решил потратить немного времени на тесты, которые проходят для очевидного решения и могли бы подтвердить корректность более быстрого решения.

Запуск

В корне проекта:

git submodule update --init --recursive
mkdir build
cd build
cmake ..
make all

Дальше в зависимости от цели:

  • Запуск с ручным вводом:

    ./src/solution

  • Запуск тестов:

    ./tests/solution_test