Условие:
Формат входного файла:
Формат выходного файла:
Тесты:
| № | Входные данные | Выходные данные |
| 1 |
2 0
11
01
|
0 |
| 2 |
2 0
11
11
|
-1 |
| 3 |
2 1
11
01
R
|
-1 |
| 4 |
3 3
000
010
000
RDU
|
2 |
| 5 | 5 5 00010 10001 00100 10100 01101 RDUUU |
4 |
Решение:
Если попробовать решить эту задачу «в лоб», то решение не будет удовлетворять пределу по времени, так как в худшем случае, нам надо перебрать $$ 10^{4} $$ возможных начальных позиций и совершить из них $$ 10^{5} $$ ходов, что в результате дает $$ 10^{9} $$ операций.
Решение «в лоб»:
- Заведем список позиций в лабиринте, которым соответствуют элементы матрицы, в которые может попасть робот. В изначальном состоянии, без просмотра пути передвижения робота, это будут все позиции в лабиринте, где значение равно $$ 0 $$. После чего, проходя путь робота по шагам, будем для всех позиций в списке проверять:
- Если мы вышли за границу матрицы, или в клетке, в которую мы собираемся перейти стоит $$ 1 $$, тогда удаляем эту позицию, поскольку она для нас недостижима.
- Иначе ничего не делаем.
- Если количество текущих вариантов пути стало равным $$ 1 $$, то мы запоминаем количество ходов при которой была достигнута данная ситуация.
- Так будем делать до тех пор, пока робот закончил свой путь.
- Если после всех проделанных нами операций остался один вариант полностью пройденного пути, тогда ответ найден. А именно это будет ход, после которого у нас кол-во удовлетворяющих позиций стало равным $$ 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 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 |
#include <iostream> #include <vector> #include <string> #include <algorithm> #include <stack> #include <set> #include <list> #include <map> #define ll long long int #define X first #define Y second #include <iostream> using namespace std; int main() { int n, k; cin >> n >> k; char maze[n][n];//лабиринт for(int i = 0; i < n; ++i){ getchar(); for(int j = 0; j < n; ++j){ maze[i][j] = getchar(); } } getchar(); char path[k+1]; //путь for(int i = 0; i < k; ++i){ path[i + 1] = getchar(); } set<pair<int, int> > visited; //ячейки, в которых мы побывали map<int, pair<int, int> > nodes; // узлы, которые должен пройти робот (номер хода, координаты) pair<int, int> cur = {0, 0}; visited.insert(cur); nodes[0] = cur; //проходим весь путь for(int i = 1; i <= k; ++i){ if(path[i] == 'L'){ --cur.X; if(!visited.count(cur)){ nodes[i] = cur; visited.insert(cur); } }else if(path[i] == 'R'){ ++cur.X; if(!visited.count(cur)){ nodes[i] = cur; visited.insert(cur); } }else if(path[i] == 'U'){ --cur.Y; if(!visited.count(cur)){ nodes[i] = cur; visited.insert(cur); } }else if(path[i] == 'D'){ ++cur.Y; if(!visited.count(cur)){ nodes[i] = cur; visited.insert(cur); } } } int count = 0; map<int, int> ans; bool ok = false; for(; nodes.size();){ for(int i = 0; i < n; ++i){ for(int j = 0; j < n; ++j){ for(pair<int, pair<int, int> > a : nodes){ if(j + a.Y.X < 0 || j + a.Y.X >= n || // не вышли ли за пределы по строкам i + a.Y.Y < 0 || i + a.Y.Y >= n || // не вышли ли за пределы по столбцам maze[i + a.Y.Y][j + a.Y.X] == '1'){ //не попали ли на 1-цу --count; break; } } ++count; } } auto t = --nodes.end(); ans[count] = t->X; nodes.erase(t); count = 0; if(ans.size() == 2) break; if(!ok){ ok = 1; if(ans.begin()->X != 1){ cout << -1 << endl; return 0; } } } if(ans.size() == 1 && ans.begin()->X == 1){ cout << ans.begin()->Y << endl; }else if(ans.size() == 2 && ans.begin()->X == 1){ cout << ans.begin()->Y << endl; }else{ cout << -1 << endl; } } |
— Нужно разобраться с пробелами. Например, перед закрывающей кавычкой, запятой, двоеточием пробелы не ставят. Можно прочесть статью Википедии про пробел.
— В коде тоже проблемы с пробелами, но не такие неприемлемые.
— Пожалуйста, не используйте стилистических настроек (цветов и т.п.) — только семантические теги. Настройки внешнего вида будут общими для всего сайта.
— Вы пишите «должен смочь». Это не самое удачное словосочетание — оставьте только «должен».
— Как минимум первое предложение слишком «наверчено» с двумя «зачем». Нужно выразить мысль чётче.
— Ссылка на submission не доступна обычному читателю.
— Рубрика «Организационные» излишня.
— Нужно написать откуда взята задача и указать автора, если он известен.
– Пробелы исправлены (вроде бы все).
– Цветовые настройки убрала.
– Первое предложение исправлено.
– Ссылку на submission удалила.
– Рубрику «Организационные» убрала.
– Добавила ссылку на условие задачи. Автор неизвестен.
Лучше. Но всё ещё плохо.
— «задача не зайдет по времени» — решение не зайдёт, не задача
— «будет за…» -> потребует примерно 109 операций. И нужно коротко объяснить или хоть намекнуть, как получилась эта оценка
— Везде по тексту » точки матрицы» нужно заменить на «клетки лабиринта». Я понимаю, что Вы представили себе лабиринт в виде матрицы, просто не пишите об этом. Вот только точек у матрицы нет, есть элементы. Т.е. (кроме правильных терминов) нужно обязательно писать если Вы сделали переход от условий задачи к какой-то модели (матричной, графовой и т.п.)
— «осталась одна точка, которая смогла пройти весь путь». Я даже не знаю, что тут посоветовать. До чтения пояснения мне было понятно, как решать задачу 🙂
У меня такое предложение. Придите как-нибудь в среду на занятия факультатива и со мной или с Александром Сергеевичем пройдитесь по тексту пояснения.
Что же, теперь текст переделан и стал более понятен. По крайней мере мне понятно описание алгоритма «в лоб» и в общих чертах Вашего алгоритма — основная идея вполне понятна. Но вот что такое карта конкретно и тем более как она конкретно накладыввается мог только догадываться — пока не посмотрел на код. Не знаю, может у Игоря Евгеньевича будет другое впечатление — но мне последний абзац показался понятным, но не исчерпывающим.
А теперь по сути задачи. Вы можете оценить сложность Вашего алгоритма (который не «в лоб»)? Вы уверены, что он работает быстрее? Кстати, у Вас была возможность проверить задачу на сервере kpi и она получила вердикт Accepted?
Я добавила скрин с codeforeces. Ссылку кинуть не могу, потому что, чтобы открыть ее, нужно сдать задачу, т.е. ссылка на submission не доступна обычному читателю.
Время с которым мое решение зашло составляет 60 мс в диапазоне от 30 мс до 90 мс.
По поводу сложности я не могу дать точную оценку, я знаю, что решение заходит, в следствии того, что оно очень быстро сходится (даже в нулевой матрице 100×100).
Понятно. Получить оценку вычислительной сложности довольно полезно и интересно в теоретическом плане. Уверен, Вы уже читали соответствующие разделы у Кормена. Если не удалось разобраться, то стоит посмотреть на эту тему вторую главу книги Скиены по алгоритмам или раздел 1.4 у Седжвика.