Задача
Обсуждая личную жизнь всевозможных злодеев, мы обделили своим вниманием графа Дуку. Так вот, граф Дуку на досуге любит складывать оригами. Он давно систематизировал свои познания в этой области следующим образом: всего граф знает n фигурок, причем для некоторых из них он знает, как получать из одной другую. Для обучения начинающих ситхов Дуку разработал специальную таблицу. В ячейке $[i, j]$ таблицы стоит «1», если граф может получить из фигурки $i$ фигурку $j$ одним сгибом. Иначе там стоит «0». Изначально в руках у графа Дуку чистый лист, то есть фигурка номер $x$ по его системе, сложить же он желает журавлика – фигурку номер $y$.
Найдите, за сколько операций граф достигнет желаемого.
Входные данные
В первой строке находится число $n (1 \leq n \leq 1000)$. В следующих $n$ строках задана таблица Дуку. В $(n + 1)$ — ой строке стоят числа $x$ и $y$.
Выходные данные
Выведите минимальное количество операций, которые придется осуществить. Если же коварным планам Графа не суждено осуществиться, выведите «-1».
Тесты
| № | Ввод | Вывод |
| 1 | 4 0 0 1 0 0 0 0 1 1 0 0 1 0 1 1 0 1 2 |
3 |
| 2 | 4 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 2 |
-1 |
| 3 | 5 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 1 5 |
4 |
| 4 | 2 0 1 1 0 2 1 |
1 |
| 5 | 6 0 1 1 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 5 2 |
-1 |
Код
|
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 |
#include <iostream> #include <queue> using namespace std; int main() { int n, x, y, v; cin >> n; int matrix[n + 1][n + 1], dist[n + 1]; queue <int> plan; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> matrix[i][j]; cin >> x >> y; for (int i = 1; i <= n; i++) dist[i] = -1; plan.push(x); dist[x] = 0; while (!plan.empty()) { v = plan.front(); plan.pop(); for (int i = 1; i <= n; i++) { if (dist[i] == -1 && matrix[v][i]) { plan.push(i); dist[i] = dist[v] + 1; } } if (v == y) plan.empty(); // если обработали вершину y, прекращаем обход } cout << dist[y]; return 0; } |
Решение
Для решения данной задачи достаточно реализовать поиск в ширину на графе. Вершины, которые нужно обработать, будем хранить в очереди, а расстояния от заданной вершины к остальным — в массиве расстояний.
Ссылки
Условие задачи на e-olymp
Код на Ideone
Описание алгоритма на сайте e-maxx.ru
Хорошо.
— Используйте, пожалуйста $\leqslant$ в формулах.
— Дайте, пожалуйста, ссылку на описание BFS, которым пользовались.
— Вроде запятая пропущена, нет?
Спасибо за замечания, все исправила.