C++: задача с блохами
Продолжаю решать задачи на веб-сервисе «CodeRun» от «Яндекса». Предыдущие посты в этой серии:
В этот раз опишу, как решил задачу из группы «легких», которая называется «Блохи».
Формулировка задачи
Есть клеточное поле размерами N × M клеток. Каждый из этих размеров находится в диапазоне от 2 до 250, включая границы. На этом поле сидит Q блох в различных клетках (их координаты заданы). Число Q находится в диапазоне от 0 до 10’000, включая границы. В клетке поля с координатами S, T есть кормушка для блох. Блохи могут перемещаться по полю ходами шахматного коня. Длина пути блохи до кормушки определяется количеством ее ходов. Определить сумму длин кратчайших путей всех блох до кормушки. Если хотя бы одна из блох не может попасть к кормушке, вывести число -1.
Пример ввода данных и вывода результата:
4 4 1 1 16
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4
42
В первой строке ввода получаем размеры поля (4 × 4), координаты клетки с кормушкой (1, 1) и число блох (16). Далее в 16 строках ввода получаем пары чисел — координаты каждой блохи. В последней строке программа вывела результат расчетов: число 42, это сумма длин кратчайших путей 16 заданных блох до кормушки.
Отмечу, что координаты кормушки и блох пользователь задает, отсчитывая клетки поля с единицы.
Вариант решения, заведший меня в тупик
Первый вариант решения этой задачи я написал довольно быстро. Я размышлял следующим образом. В предыдущей задаче я уже находил кратчайший путь между двумя заданными вершинами в неориентированном графе. В текущей задаче тоже речь идет о кратчайшем пути, только не об одном, а о многих. Следовательно, можно попробовать вложить предыдущее решение в цикл перебора блох, подсчитать сумму кратчайших путей и выдать результат.
На пути реализации этой идеи наибольшие трудности у меня возникли с организацией хранения данных. В предыдущей задаче речь шла про граф, здесь — про клеточное поле. Нужно было решить, что в этой задаче будет графом, и в каких структурах данных хранить всё необходимое.
Я отправил первый вариант решения на автоматическую проверку, и оказалось, что моя программа не укладывается в ограничение по времени. Как и в предыдущих задачах, здесь это ограничение тоже составляет 1 секунду.
После этой неудачи я решил замерить время работы получившейся программы сам, чтобы найти медленные части программы и оптимизировать их в плане быстродействия. Для замера времени работы использовал тот же код, что и ранее.
Для замера времени работы программы при большом количестве входных данных (например, если блох 10 тысяч) ручной ввод данных отпадает. Я временно переделал программу на получение данных из текстового файла (в C++ это несложно). Файл со входными данными вручную писать тоже не хотелось, поэтому написал простую вспомогательную программу для этого:
#include <fstream>
int main()
{
std::ofstream file("input.txt");
for (int n{ 1 }; n <= 100; n++)
for (int m{ 1 }; m <= 100; m++)
file << n << ' ' << m << '\n';
return 0;
}
В полученный текстовый файл с координатами 10 тысяч блох добавил вручную первую строку и получились следующие тестовые входные данные (всего в файле 10’001 строка):
100 100 1 1 10000
1 1
1 2
1 3
1 4
1 5
...
100 95
100 96
100 97
100 98
100 99
100 100
Программа считывает из этого файла количество координат, заданное количеством блох. То есть для постепенного увеличения вычислительной нагрузки на программу я могу просто вручную постепенно менять в этом файле количество блох, каждый раз замеряя время работы программы. Я писал новые версии программы, постепенно оптимизируя ее. Получилось следующее.
Результаты первой версии:
входные данные сумма путей время работы, сек
-------------------------------------------------
100 100 1 1 10 31 0.0308588
100 100 1 1 20 112 0.374496
100 100 1 1 30 241 1.65837
100 100 1 1 40 422 5.07949
100 100 1 1 50 651 12.6617
Результаты самой быстрой версии:
входные данные сумма путей время работы, сек
-------------------------------------------------
100 100 1 1 10 31 0.0014459
100 100 1 1 20 112 0.0056012
100 100 1 1 30 241 0.0148914
100 100 1 1 40 422 0.0333524
100 100 1 1 50 651 0.062138
100 100 1 1 60 932 0.104476
100 100 1 1 70 1261 0.149094
100 100 1 1 80 1642 0.202587
100 100 1 1 90 2071 0.26378
100 100 1 1 100 2552 0.327574
100 100 1 1 1000 25620 3.43029
100 100 1 1 10000 365286 58.4006
Конечно, процесс оптимизации бесконечен. Однако, я понял, что проблема у меня в данном случае не в недостаточно хорошей реализации, а в самом алгоритме решения. Стало понятно, что нужно искать другой подход.
Алгоритм решения задачи
Вероятно, у этой задачи есть ряд решений. Как обычно, своё я нашел не сам, мне подсказали. Код, как обычно, писал сам.
Если на клеточном поле найден кратчайший путь (состоящий из ходов шахматного коня) из заданной начальной клетки в заданную конечную клетку, то этот же путь будет кратчайшим из конечной клетки в начальную. Предлагается выполнить обход в ширину из конечной клетки, а не из начальных. Поскольку конечная клетка с кормушкой одна, то вместо выполнения для 10 тысяч блох 10 тысяч поисков в ширину понадобится выполнить только один обход в ширину из конечной клетки.
Когда до меня дошла эта идея, у меня случился взрыв мозга от восторга. 😱💥. Тут должна быть mind blown gif.
Запишу алгоритм словами:
-
Предварительный расчет. Выполнить обход клеток поля в ширину из конечной клетки. При этом для каждой клетки поля, достижимой из конечной, запомнить длину кратчайшего пути. Если клетка поля недостижима из конечной, запомнить для нее длину кратчайшего пути в виде числа
-1. -
Перебрать координаты клеток поля с блохами в цикле. Подсчитать сумму длин кратчайших путей всех блох и вывести в качестве результата работы программы. Длины брать из результатов предварительного расчета, выполненного в пункте 1. Если для какой-либо блохи путь в конечную клетку не существует (-1), прервать цикл и вывести число
-1.
Напомню, обход в ширину и поиск в ширину похожи, но поиск в ширину фокусируется на поиске заданной вершины графа и заканчивается, когда найдена заданная вершина. При поиске в ширину граф может не быть обойден весь. Обход в ширину нужен именно для обхода всех вершин графа, что и требуется в данном случае в пункте 1.
Такой алгоритм не будет сильно зависеть от заданного количества блох. Разница между временем работы программы при разных входных данных должна быть настолько небольшой, что ею можно будет пренебречь. Это всё потому, что обход в ширину всегда будет только один.
Как обычно, постфактум решение кажется очень простым. Но чтобы его найти, мне понадобилось много времени. Это, наверное, говорит о моей неопытности в алгоритмах.
Моя реализация решения на C++
Вершинами графа в данном случае я считаю все клетки поля. Ребрами тогда становятся прыжки блох в виде ходов шахматного коня. В отличие от предыдущей задачи тут не задана матрица смежности, но она и не требуется: ребра определены ходами шахматного коня из любой клетки поля. На поле могут быть недостижимые из клетки с кормушкой клетки, их считаю изолированными вершинами графа.
Обход клеток-потомков текущей клетки (родителя) произвожу в цикле из 8 шагов (из любой клетки на поле это максимально возможное число ходов шахматным конем). Внутри этого цикла проверяю, является ли очередной ход возможным (не происходит ли выхода за границы поля-доски).
Довольно много перебрал вариантов организации структур данных. Остановился на следующем. Для обхода в ширину и хранения результатов предварительного расчета создал таблицу (вектор векторов), каждая ячейка которой является структурой с названием vertex. В структуре vertex храню данные о том, находится ли данная клетка в очереди, посещена ли клетка при обходе в ширину. В этой же структуре храню длину кратчайшего пути до этой клетки из клетки с кормушкой.
При обходе в ширину вершин графа удобно вести подсчет кратчайшего пути (количество ребер в невзвешенном графе) из начальной вершины обхода (у меня это клетка с кормушкой) до достигнутых при очередном расширении вершин. Я беру длину кратчайшего пути из вершины-родителя и прибавляю к ней единицу — так получается длина кратчайшего пути до текущей вершины-потомка из вершины с кормушкой.
Для уменьшения количества используемой памяти (и упрощения кода) я придумал в очередь помещать не вершины-клетки, а их координаты на поле. Для работы с координатами я создал структуру vertex_coords.
#include <iostream>
#include <vector> // для std::vector
#include <queue> // для std::queue
// описание вершины графа (клетка поля)
struct vertex
{
bool inQueue; // находится ли в очереди
bool visited; // посещена ли клетка
int path_len; // длина кратчайшего пути из клетки с кормушкой
};
// координаты (отсчет с 0) клетки поля
struct vertex_coords
{
int n; // номер строки
int m; // номер столбца
};
int main()
{
// размеры поля, каждый из которых в диапазоне [2..250]
int N{};
int M{};
// координаты (отсчет с 1) клетки с кормушкой
int S{};
int T{};
// количество блох на поле, в диапазоне [0..10'000]
int Q{};
// получить данные:
std::cin >> N >> M >> S >> T >> Q;
// привести пользовательскую нумерацию (с единицы) к нумерации с нуля
S--;
T--;
// создать таблицу вершин графа (клеток поля) с инициализацией вершин,
// изначально все вершины не в очереди (false), не посещены (false),
// а длина кратчайшего пути неизвестна (-1)
std::vector<std::vector<vertex>> field(
N,
std::vector<vertex>(M, { false, false, -1 })
);
// координаты текущей клетки при обходе клеток
vertex_coords coords{ S, T };
// создать пустую очередь и поместить в нее клетку с кормушкой
std::queue<vertex_coords> qu;
qu.push(coords);
field[coords.n][coords.m].inQueue = true;
field[coords.n][coords.m].path_len = 0; // длина пути до себя же
// выполнить обход в ширину всего поля, начиная с клетки-кормушки,
// с сохранением длин кратчайших путей до каждой достижимой клетки
do
{
// извлечь из очереди клетку и пометить ее как посещенную
coords = qu.front();
qu.pop();
field[coords.n][coords.m].inQueue = false;
field[coords.n][coords.m].visited = true;
// поместить в очередь клетки-потомки текущей клетки с ограничениями,
// потомков может быть до 8 (ходы коня, ограниченные краем доски)
const int num_moves{ 8 };
int v[num_moves]{ -1, 1, 2, 2, 1, -1, -2, -2 }; // сдвиг по высоте
int h[num_moves]{ 2, 2, 1, -1, -2, -2, -1, 1 }; // сдвиг по ширине
// запомнить координаты клетки-родителя
vertex_coords par_coords{ coords };
for (int move{}; move < num_moves; move++)
{
coords = { par_coords.n + v[move], par_coords.m + h[move] };
// проверить ограничения на помещение в очередь:
// координаты не должны выходить за край доски, клетка должна
// не быть посещенной, клетка не должна уже находиться в очереди
if (coords.n >= 0 && coords.n < N && coords.m >= 0 && coords.m < M
&& !field[coords.n][coords.m].visited
&& !field[coords.n][coords.m].inQueue)
{
qu.push(coords);
field[coords.n][coords.m].inQueue = true;
field[coords.n][coords.m].path_len =
field[par_coords.n][par_coords.m].path_len + 1;
}
}
} while (!qu.empty());
// определить сумму длин кратчайших путей всех блох до кормушки
int sum{};
for (int q{}; q < Q; q++) // цикл перебора блох
{
// получить начальные координаты блохи
std::cin >> coords.n >> coords.m;
// привести пользовательскую нумерацию (с единицы) к нумерации с нуля
coords.n--;
coords.m--;
if (field[coords.n][coords.m].path_len >= 0)
{
sum += field[coords.n][coords.m].path_len;
}
else // путь для этой блохи не найден (-1)
{
sum = -1;
break;
}
}
// вывести общую сумму длин кратчайших путей (она может быть равна -1)
std::cout << sum << '\n';
return 0;
}
Эта версия программы успешно прошла автоматическую проверку на сайте «CodeRun» от «Яндекса». Результаты этой версии программы с замером времени:
входные данные сумма путей время работы, сек
-------------------------------------------------
100 100 1 1 10 31 0.0032469
100 100 1 1 20 112 0.0035581
100 100 1 1 30 241 0.0037737
100 100 1 1 40 422 0.0035545
100 100 1 1 50 651 0.0037454
100 100 1 1 60 932 0.0039435
100 100 1 1 70 1261 0.0038331
100 100 1 1 80 1642 0.0034847
100 100 1 1 90 2071 0.0040471
100 100 1 1 100 2552 0.0039171
100 100 1 1 1000 25620 0.0043649
100 100 1 1 10000 365286 0.0154875
Как видно из этих результатов, эта версия программы с большим запасом уложилась в 1 секунду.