Условие
Матрица размера [latex]n\times m[/latex] определяет некоторый лабиринт. B матрице элемент [latex]1[/latex] обозначает стену, а [latex]0[/latex] определяет свободное место. В первой строке матрицы определяются входы [latex]x_i[/latex], а в последней выходы [latex]y_i[/latex], [latex]i = 1, \ldots, k[/latex], [latex]k \leqslant n[/latex] которые должны быть нулевыми элементами.
Необходимо определить, можно ли:
а) провести [latex]k[/latex] человек от входа [latex]x_i[/latex] до выхода [latex]y_i[/latex] соответственно, [latex]i = 1, \ldots, k[/latex], таким образом, чтобы каждое свободное место посещалось не более одного раза.
б) то же, но человека можно выводить чеpез любой из выходов. Примечание: Движение в лабиринте осуществляется только по вертикали или горизонтали.
Входные данные
Числа [latex]n[/latex] и [latex]m[/latex] определяющие кол-во строк и столбцов соответственно, [latex]1 \leqslant n, m \leqslant 10^4[/latex]. Количество входов [latex]k[/latex] равно кол-ву выходов, [latex]1 \leqslant k \leqslant \min(1000, n)[/latex]. Число [latex]k[/latex] не является частью входных данных (не подается на вход программы).
Выходные данные
[latex]YES[/latex], если соответствующий набор маршрутов существует, [latex]NO[/latex] — в противном случае.Замечания
- Легко заметить, что случай б) эквивалентен случаю а). Предположим, что [latex]k > 1[/latex] и мы провели первых [latex]i — 1[/latex] людей (возможно, никого) согласно условию а), [latex]1 \leqslant i < k[/latex]. Пусть человек под номером [latex]i[/latex] нарушил условие, например, вышел через выход с номером [latex]i + 1[/latex]. Тогда, т.к. его путь цельный и идет от самого первого ряда лабиринта до последнего, он образует «стену» из единичек, заблокировав выход [latex]i[/latex]. Тогда провести всех людей не возможно, ведь кол-ва входов и выходов равны. Следовательно, будем рассматривать как нашу задачу только случай а).
- Заполнение клеток каждого из пройденных маршрутов в матрице различными числами вместо единицы и функция
не имеют отношения к поставленной задаче, так было сделано чтобы при желании можно было посмотреть, какой именно набор маршрутов программа нашла (см. код и тестовые данные, последняя колонка).1void print(int n, int m, int** matrix)
Тесты
| № теста | Входные данные | Выходные данные | Пояснение (маршрут) |
| 1 | 6 8 1 0 1 0 1 1 0 1 1 0 1 0 0 0 0 1 1 0 1 1 0 0 1 1 1 0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 1 |
YES | 1 a 1 b 1 1 c 1 1 a 1 b b c c 1 1 a 1 1 b c 1 1 1 a b b b c 0 1 1 a b 1 1 c c 1 1 a b 1 1 1 c 1 |
| 2 | 5 7 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 |
YES | 1 a b c 1 1 d a a b c d d d a b b c d 1 1 a b c c d d d a b c 1 1 1 d |
| 3 | 7 7 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 0 1 0 |
YES | 1 1 a b 1 1 1 a a a b 0 0 0 a a b b 0 0 0 1 a b b b b 0 a a a a a b 0 a a a 1 a b b 1 1 1 1 a 1 b |
| 4 | 5 5 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 |
NO | |
| 5 | 7 12 1 1 1 1 1 0 1 1 1 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 1 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 |
YES | 1 1 1 1 1 a 1 1 1 1 1 b 0 0 0 1 a a 1 0 0 0 0 b 0 0 0 a a 1 1 0 1 1 1 b 0 1 1 a 0 0 1 1 1 0 0 b 1 0 1 a 0 0 1 0 0 0 1 b 0 0 0 a a a 1 0 0 1 1 b 1 1 1 1 1 a 1 1 1 1 1 b |
| 6 | 3 6 1 1 1 1 1 0 0 0 0 0 0 0 1 0 1 1 1 1 |
YES | 1 1 1 1 1 a 0 a a a a a 1 a 1 1 1 1 |
| 7 | 10 10 0 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 0 |
YES | a 1 1 1 1 1 1 1 1 1 a 1 a a a a a a a a a 1 a 1 1 1 1 1 1 a a 1 a 1 a a a a 1 a a 1 a 1 a 0 1 a 1 a a 1 a 1 a 0 1 a 1 a a 1 a a a 0 1 a 1 a a 1 1 1 1 1 1 a 1 a a a a a a a a a 1 a 1 1 1 1 1 1 1 1 1 a |
| 8 | 10 10 0 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 0 |
NO | |
| 9 | 6 7 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 |
YES | 1 1 1 1 a b 1 a a a 1 a b 1 a 1 a a a b 1 a a 1 b b b 1 1 a a b 0 1 1 1 1 a b 1 1 1 |
| 10 | 1 5 0 0 0 0 0 |
YES | a b c d e |
Алгоритм
Оптимальной стратегией будет оставлять как можно больше места последующим людям, т.е. для каждого из людей всегда стараться занять либо самые левые, либо самые правые места, «держась» при этом стены лабиринта. Для удобства, будем рассматривать стратегию «поиска влево». Считаем матрицу чисел, и для каждого входа необходимо будет:
- Попытаться провести человека согласно описанной выше стратегии.
- В случае успеха, отметить все ячейки, пройденные ним, как недоступные. Иначе — будем кидать исключение, ловить которое будем непосредственно в основной функции, при поимке — выводим [latex]NO[/latex] и завершаем работу программы.
За поиск маршрута отвечают 2 функции. Функция
|
1 |
stack<pair<int,int>> findRoute(int n, int m, int** matrix, int begin) |
возвращает стек координат (пар чисел), представляющих собой маршрут человека, или кидает исключение в случае его отсутствия. Функция только создает стек, помещает в него первую вершину и запускает рекурсивную функцию
|
1 |
bool search(int n, int m, int** matrix, stack<pair<int,int>>& route, int dir) |
отвечающую непосредственно за поиск, из точки входа с направлением движения вниз (т.к. из входа первый шаг можно совершить только вниз). Алгоритм поиска маршрута:
- Находим, в какую клетку мы попали при данном направлении. Определим все направления как подходящие константы и будем получать направление по формуле [latex]dir / 10, dir \mod 10[/latex], первая координата — по вертикали, вторая — по горизонтали. Так, например, для [latex]down = 10[/latex] получим вектор [latex](1, 0)[/latex], соответствующий перемещению на одну ячейку вниз в матрице (для остальных направлений значения подобраны аналогично).
- Проверяем, можем ли мы находиться в этой ячейке, если нет (она занята или находится вне матрицы) — не ищем дальше, возвращаем [latex]false[/latex].
- Добавляем координаты ячейки в стек route, проверяем, является ли данная точка выходом, если да — завершаем поиск успешно ([latex]true[/latex]).
- Составим массив направлений, от наиболее до наименее приоритетных, в зависимости от предыдущего направления. Например, текущее направление было [latex]down[/latex], мы пришли сверху, лучше всего будет попробовать пойти влево, иначе снова вниз, иначе вправо, наверх нельзя (уже были):
Для других направлений — рассуждения аналогичны.42priorityDirs = new int[3]{left, down, right}; - Поочередно вызовем поиск из новой точки в каждом из направлений в порядке приоритета, при нахождении пути оставшиеся направления (с меньшим приоритетом) не рассматриваем, возвращаем [latex]true[/latex].
- Если ни в одном из направлений нельзя попасть к выходу (тупик) — удаляем вершину из стека, возвращаем [latex]false[/latex].
Код
|
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
#include <iostream> #include <stack> #include <utility> #define down 10 #define left -1 #define right 1 #define up -10 using namespace std; void print(int n, int m, int** matrix) { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (matrix[i][j] == 0 || matrix[i][j] == 1) cout << matrix[i][j] << " "; else cout << (char)matrix[i][j] << " "; } cout << endl; } } bool search(int n, int m, int** matrix, stack<pair<int,int>>& route, int dir) { pair<int, int> npos = make_pair(dir / 10 + route.top().first, dir % 10 + route.top().second); if (npos.first < 0 || npos.first >= n || npos.second < 0 || npos.second >= m || matrix[npos.first][npos.second] != 0) return false; else { route.push(npos); matrix[npos.first][npos.second] = 1; //чтобы при построении маршрута нельзя было вернутся в предыдущие вершины if (npos.first == n - 1) return true; else { int* priorityDirs; switch (dir) { case down: priorityDirs = new int[3]{left, down, right}; break; case left: priorityDirs = new int[3]{left, down, up}; break; case right: priorityDirs = new int[3]{down, right, up}; break; case up: priorityDirs = new int[3]{left, right, up}; break; } bool found = true; for (int i = 0; i < 3; i++) { found = search(n, m, matrix, route, priorityDirs[i]); if (found) return true; } matrix[npos.first][npos.second] = 0; //если ячейка не подходит, убираем ее из маршрута (освобождаем) route.pop(); return false; } } } stack<pair<int,int>> findRoute(int n, int m, int** matrix, int begin) { stack<pair<int,int>> route; route.push(make_pair(0, begin)); if (n != 1 && !search(n, m, matrix, route, down)) //n != 1 для корректного ответа на тесты вида №10 throw -1; return route; } int main() { ios::sync_with_stdio(false); int n, m; scanf("%d%d", &n, &m); int** matrix = new int*[n]; for (int i = 0; i < n; i++) matrix[i] = new int[m]; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) scanf("%d", &matrix[i][j]); bool possible = true; int symbol = -1; //определяет символ, которым будет отмечен маршрут человека при необходимости вывода лабиринта на экран for (int i = 0; i < m; i++) { if (matrix[0][i] == 0) { symbol++; try { stack<pair<int,int>> route = findRoute(n, m, matrix, i); while (!route.empty()) //вынимаем из стека координаты пройденных ячеек и отмечаем их в матрице { pair<int, int> pos = route.top(); matrix[pos.first][pos.second] = 'a' + symbol; //для удобства при необходимости вывода маршрута route.pop(); } } catch (...) { possible = false; break; } } } cout << (possible ? "YES" : "NO") << endl; /* if (possible) print(n, m, matrix); */ return 0; } |
Ссылки
Код для тестирования на ideone.
Функция bool_search(…).
Мы разве можем использовать указатель на priority_dirs как параметр рекурсивной функции? Ведь когда указатель — параметр, то он указывает на первый элемент.
Здесь нет ошибки. В функцию передается адрес начала области памяти, где размещена матрица. Фактически, это просто число, которое не изменяется после отведения памяти под массив строк.
Добрый день!
Спасибо за ваш ответ.
Но почему тогда у меня, когда компилирую код в Visual Studio 2017, выдается ошибка, в которой указано, что когда приходит момент использования рекурсивной функции, используется неинициализированная переменная priorityDirs?