Условие:
Формат входного файла:
Формат выходного файла:
Тесты:
№ | Входные данные | Выходные данные |
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; } } |