Лабиринт

02/07/2016 by Маша Лукьянова

Условие:

Имя входного файла: стандартный поток ввода

Имя выходного файла: стандартный поток вывода

Ограничение по времени: 2 second

Ограничение по памяти: 64 мегабайт

Задан лабиринт [latex] N \times N [/latex], некоторые клетки которого могут быть заняты. Дан путь робота длины [latex] k [/latex] по этому лабиринту без указания его начального положения. Известно, что робот до начала движения стоит в одной из свободных клеток. Необходимо определить наименьшее количество передвижений по пути, после которого можно точно определить, где находится робот.

Задача взята из 1-го раунда KPI OPEN 2013 года.

Формат входного файла:

Первая строка входного файла содержит два целых числа через пробел $$ N (1 \leq N \leq 100) $$ и $$k (0 \leq k \leq 10^{5}) $$. В следующих [latex] N [/latex] строках задана карта лабиринта как совокупность 0 и 1 без пробелов: 1 – занятая клетка, 0 – свободная. В последней строке дана последовательность из $$ k (0 \leq k \leq 10^{5} ) $$ символов. Символы задают движение робота по лабиринту: символ [latex] U [/latex] — вверх, [latex] D [/latex] — вниз, [latex] R [/latex] —вправо, [latex] L [/latex] — влево. Других символов в строке передвижений нет, все символы в верхнем регистре латиницы.

Формат выходного файла:

В единственной строке выходного файла выведите единственное целое число не меньше нуля — наименьшее количество передвижений по пути, после которого можно точно определить местоположение робота. Если ответ не существует, либо входные данные некорректны, выведите -1.

Тесты:

№	Входные данные	Выходные данные
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 $$. В любом другом случае ответ нельзя определить однозначно.

Другая идея состоит в том, чтобы построить карту «переходов», в которой будет храниться номер хода, на котором робот впервые попал в эту клетку и ее координаты. Эта карта играет роль некоторого шаблона полного пути робота и «накладывая» его на каждый элемент матрицы в качестве начальной позиции, мы проверяем мог ли данный элемент матрицы служить «пунктом отправления» робота. Если такой элемент есть и он единственен, значит, можно однозначно определить начальное положение робота, но для того чтобы определить минимальное количество требуемых ходов-нужно последовательно удалять последние ходы из карты, «накладывая» изменившийся шаблон на каждый элемент, до тех пор, пока количество элементов удовлетворяющих шаблону не возрастет. Что значит, что мы получим номер решающего хода после которого судьба робота решится однозначно, значит ответом будет предыдущий ход. Стоит отметить, что если в карте останется всего лишь один элемент (соответствующий первому ходу), то расположение робота определялось однозначно первым ходом.

#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;
    }
}

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.

Related Images:

e-olymp 1060. Линии

28/06/2016 by Кондратюк Настя

Задача взята с сайта e-olymp.com.

Условие задачи

В таблице из [latex]n[/latex] строк и [latex]n[/latex] столбцов некоторые клетки заняты шариками, другие свободны. Выбран шарик, который нужно переместить, и место, куда его переместить. Выбранный шарик за один шаг перемещается в соседнюю по горизонтали или вертикали свободную клетку. Требуется выяснить, возможно ли переместить шарик из начальной клетки в заданную, и если возможно, то найти путь из наименьшего количества шагов.

Входные данные

В первой строке находится число [latex]n \left (2\leq n\leq 40 \right )[/latex], в каждой из следующих [latex]n[/latex] строк — по [latex]n[/latex] символов. Символом точки обозначена свободная клетка, латинской заглавной [latex]O[/latex] — шарик, [latex]@[/latex] — исходное положение шарика, который должен двигаться, латинской заглавной [latex]X[/latex] — конечное положение шарика.

Выходные данные

В первой строке выводится [latex]Y[/latex], если движение возможно, или [latex]N[/latex], если нет. Если движение возможно далее следует [latex]n[/latex] строк по [latex]n[/latex] символов — как и на вводе, но [latex]X[/latex], а также все точки на пути заменяются плюсами.

Тесты

Входные данные

Выходные данные

5
....X
.OOOO
.....
OOOO.
@....

....X

.OOOO

.....

OOOO.

@....

Y
+++++
+OOOO
+++++
OOOO+
@++++

+++++

+OOOO

+++++

OOOO+

@++++

5
..X..
.....
OOOOO
.....
..@..

..X..

.....

OOOOO

.....

..@..

N

5
...X.
.....
O.OOO
.....
....@

...X.

.....

O.OOO

.....

....@

Y
..++.
.++..
O+OOO
.++++
....@

..++.

.++..

O+OOO

.++++

....@

Код программы

#include <iostream>
#include <queue>
using namespace std;

/* нахождение пути*/
void find_path(int n, int row, int col, char** lab, int** visited, int** path, queue<int>& plan){
    if(!visited[row][col]){
        /* проверяем не вышли ли мы за границы лабиринта, есть ли клетка 
        в массиве посещенных и можно ли через нее пройти*/
        if ((row+1) < n && (row+1) >= 0 && !visited[row+1][col] &&
            (lab[row+1][col] == '.' || lab[row+1][col] == 'X')) {
                path[row+1][col] = path[row][col] + 1;
                plan.push(row+1);
                plan.push(col);
        }
        if((row-1) < n && (row-1) >= 0 && !visited[row-1][col] && 
            (lab[row-1][col] == '.' || lab[row-1][col] == 'X')) {
                path[row-1][col] = path[row][col] + 1;
                plan.push(row-1);
                plan.push(col);
        }
        if((col + 1) < n && (col + 1) >= 0 && !visited[row][col+1] && 
            (lab[row][col+1] == '.' || lab[row][col+1] == 'X')) {
                path[row][col+1] = path[row][col] + 1;
                plan.push(row);
                plan.push(col+1);
        }
        if((col - 1) < n && (col - 1) >= 0 && !visited[row][col-1] && 
            (lab[row][col-1] == '.' || lab[row][col-1] == 'X')) {
                path[row][col-1] = path[row][col] + 1;
                plan.push(row);
                plan.push(col-1);
        }
        visited[row][col] = 1; /* отмечаем клетку в которой побывали */
    }
}
 
int main() {
    int n, x_start, y_start, x_end, y_end, x, y;
    queue <int> plan; 
    cin >> n;
    char** lab = new char* [n];
    int** visited = new int * [n];
    int** path = new int * [n];
    for(int i=0; i<n; i++){
        lab[i] = new char [n];   /* массив для хранения лабиринта */
        visited[i] = new int [n]; /* массив для хранения информации о посещении клеток*/
        path[i] = new int [n];  /* массив для хранения найденных путей */
        for(int j=0; j<n; j++){
            visited[i][j] = 0;  
            path[i][j] = -1;   
            cin >> lab[i][j]; 
            if (lab[i][j] == '@') { /* находим начало пути*/
                x_start = i;
                y_start = j;
                plan.push(i);  /* заносим начальную клетку */
                plan.push(j);  /* в план посещения */
                path[i][j] = 1;
            }
            else if (lab[i][j] == 'X') { /* находим конечную точку */
                x_end = i;
                y_end = j;
            }
        }
    }
    while(!plan.empty()){ /* пока очередь посещения клеток непустая*/
        x=plan.front();
        plan.pop();
        y=plan.front();
        plan.pop();
        find_path(n, x, y, lab, visited, path, plan); /* продолжаем поиск пути*/
    }
    if(!visited[x_end][y_end]){
        cout << "N" << endl;
    }
    else {
        cout << "Y" << endl;
            x = x_end;
            y = y_end;
            lab[x][y] = '+';
            while (path[x][y] != 2) { /* восстановление пути*/
                if ((x-1) >= 0 && (x-1) < n && (path[x-1][y] == path[x][y] - 1)) {
                    x = x-1;
                    lab[x][y] = '+';
                }
                else if ((x+1) >= 0 && (x+1) < n && (path[x+1][y] == path[x][y] - 1)) {
                    x = x+1;
                    lab[x][y] = '+';
                }
                else if ((y-1) >= 0 && (y-1) < n && (path[x][y-1] == path[x][y] - 1)) {
                    y = y-1;
                    lab[x][y] = '+';
                }
                else if ((y+1) >= 0 && (y+1) < n && (path[x][y+1] == path[x][y] - 1)) {
                    y = y+1;
                    lab[x][y] = '+';
                }
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    cout << lab[i][j];
                }
                cout << endl;
            }
        }
    return 0;
}

100

101

102

103

104

105

106

107

#include <iostream>

#include <queue>

using namespace std;

/* нахождение пути*/

void find_path(int n, int row, int col, char** lab, int** visited, int** path, queue<int>& plan){

if(!visited[row][col]){

/* проверяем не вышли ли мы за границы лабиринта, есть ли клетка

в массиве посещенных и можно ли через нее пройти*/

if ((row+1) < n && (row+1) >= 0 && !visited[row+1][col] &&

(lab[row+1][col] == '.' || lab[row+1][col] == 'X')) {

path[row+1][col] = path[row][col] + 1;

plan.push(row+1);

plan.push(col);

}

if((row-1) < n && (row-1) >= 0 && !visited[row-1][col] &&

(lab[row-1][col] == '.' || lab[row-1][col] == 'X')) {

path[row-1][col] = path[row][col] + 1;

plan.push(row-1);

plan.push(col);

}

if((col + 1) < n && (col + 1) >= 0 && !visited[row][col+1] &&

(lab[row][col+1] == '.' || lab[row][col+1] == 'X')) {

path[row][col+1] = path[row][col] + 1;

plan.push(row);

plan.push(col+1);

}

if((col - 1) < n && (col - 1) >= 0 && !visited[row][col-1] &&

(lab[row][col-1] == '.' || lab[row][col-1] == 'X')) {

path[row][col-1] = path[row][col] + 1;

plan.push(row);

plan.push(col-1);

}

visited[row][col] = 1; /* отмечаем клетку в которой побывали */

}

int main() {

int n, x_start, y_start, x_end, y_end, x, y;

queue <int> plan;

cin >> n;

char** lab = new char* [n];

int** visited = new int * [n];

int** path = new int * [n];

for(int i=0; i<n; i++){

lab[i] = new char [n]; /* массив для хранения лабиринта */

visited[i] = new int [n]; /* массив для хранения информации о посещении клеток*/

path[i] = new int [n]; /* массив для хранения найденных путей */

for(int j=0; j<n; j++){

visited[i][j] = 0;

path[i][j] = -1;

cin >> lab[i][j];

if (lab[i][j] == '@') { /* находим начало пути*/

x_start = i;

y_start = j;

plan.push(i); /* заносим начальную клетку */

plan.push(j); /* в план посещения */

path[i][j] = 1;

}

else if (lab[i][j] == 'X') { /* находим конечную точку */

x_end = i;

y_end = j;

}

while(!plan.empty()){ /* пока очередь посещения клеток непустая*/

x=plan.front();

plan.pop();

y=plan.front();

plan.pop();

find_path(n, x, y, lab, visited, path, plan); /* продолжаем поиск пути*/

}

if(!visited[x_end][y_end]){

cout << "N" << endl;

}

else {

cout << "Y" << endl;

x = x_end;

y = y_end;

lab[x][y] = '+';

while (path[x][y] != 2) { /* восстановление пути*/

if ((x-1) >= 0 && (x-1) < n && (path[x-1][y] == path[x][y] - 1)) {

x = x-1;

lab[x][y] = '+';

}

else if ((x+1) >= 0 && (x+1) < n && (path[x+1][y] == path[x][y] - 1)) {

x = x+1;

lab[x][y] = '+';

}

else if ((y-1) >= 0 && (y-1) < n && (path[x][y-1] == path[x][y] - 1)) {

y = y-1;

lab[x][y] = '+';

}

else if ((y+1) >= 0 && (y+1) < n && (path[x][y+1] == path[x][y] - 1)) {

y = y+1;

lab[x][y] = '+';

}

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

cout << lab[i][j];

}

cout << endl;

}

return 0;

}

ideone.com

Засчитанное решение на e-olymp.com.

Решение

Для решения данной задачи можно использовать волновой алгоритм. Считывая исходный массив с лабиринтом находим индексы начального и конечного положения шарика. Затем, начиная с начальной позиции проверяем проходимы ли соседние с ней клетки . Если клетка проходима и не была посещена ранее, помещаем ее в очередь и присваиваем соответствующей клетке массива, в котором хранится путь, значение на единицу большее, чем в начальной клетке. Так каждая помеченная клетка становится начальной, порождая шаги в соседние клетки, пока очередь не опустеет.

Затем, если клетка с конечным положением шарика достижима, необходимо восстановить кратчайший путь. Двигаясь от конечной позиции в начальную, на каждом шаге выбираем клетку значение которой на единицу меньше текущего положения, при этом символы в соответствующих клетках исходного лабиринта заменяем на символ [latex]+.[/latex]

Related Images:

AL15. Лабиринт

11/04/2016 by Сплошнов Кирилл

Условие

Матрица размера [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]. Тогда провести всех людей не возможно, ведь кол-ва входов и выходов равны. Следовательно, будем рассматривать как нашу задачу только случай а).
Заполнение клеток каждого из пройденных маршрутов в матрице различными числами вместо единицы и функция

C++

void print(int n, int m, int** matrix)

1

void 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 функции. Функция

stack<pair<int,int>> findRoute(int n, int m, int** matrix, int begin)

1	stack<pair<int,int>> findRoute(int n, int m, int** matrix, int begin)

возвращает стек координат (пар чисел), представляющих собой маршрут человека, или кидает исключение в случае его отсутствия. Функция только создает стек, помещает в него первую вершину и запускает рекурсивную функцию

bool search(int n, int m, int** matrix, stack<pair<int,int>>& route, int dir)

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], мы пришли сверху, лучше всего будет попробовать пойти влево, иначе снова вниз, иначе вправо, наверх нельзя (уже были):

C++

priorityDirs = new int[3]{left, down, right};

42

priorityDirs = new int[3]{left, down, right};

Для других направлений — рассуждения аналогичны.
Поочередно вызовем поиск из новой точки в каждом из направлений в порядке приоритета, при нахождении пути оставшиеся направления (с меньшим приоритетом) не рассматриваем, возвращаем [latex]true[/latex].
Если ни в одном из направлений нельзя попасть к выходу (тупик) — удаляем вершину из стека, возвращаем [latex]false[/latex].

Код

#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;
}

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.

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Tag Archives: лабиринт

Лабиринт

Условие:

Формат входного файла:

Формат выходного файла:

Тесты:

Решение:

Related Images:

e-olymp 1060. Линии

Условие задачи

Входные данные

Выходные данные

Тесты

Код программы

Решение

Related Images:

AL15. Лабиринт

Условие

Входные данные

Замечания

Тесты

Алгоритм

Ссылки

Related Images: