Алгоритмы поиска

16/11/2019 by Мазурок Игорь Евгеньевич

Search Algorithms

Хочу предложить простой, но достаточно общий взгляд на алгоритмы поиска в ширину BFS (Breadth-first Search), в глубину DFS (Depth-first Search) и бесконечное количество других с общей схемой. Фактически это алгоритмы обхода соседних вершин графа в которых последовательно строятся пути из некоторой исходной вершины ко всем остальным.
Сначала сформулируем общую схему алгоритмов этого типа. И без обычных для учебников избыточных сложностей в виде белых-серых-черных вершин.

Заводим PLAN поиска — контейнер данных, где будем хранить вершины в которых мы планируем побывать. Изначально он пуст.
Добавляем в PLAN поиска исходную вершину с которой нам предписано начать.
Пока PLAN не пуст и цель поиска не достигнута делаем следующее
1. GET: Извлекаем из PLAN какую-нибудь вершину v.
2. Посещаем вершину v. Если мы не просто обходим вершины, а что-то ищем, то здесь самое время обыскать вершину v на предмет достижения цели поиска.
3. Как-то отмечаем, что вершина v уже посещена.
4. PUT: Добавляем в PLAN все соседние с v вершины, которые еще не были посещены.
Выводим результат поиска.

Самым важным для реализации этой схемы является PLAN. Это контейнер данных в котором нам нужны две функции GET — чтобы что-то из контейнера достать и PUT — чтобы в контейнер что-то положить. Конечно лучше использовать уже готовые контейнеры. Выбор контейнера будет определять стратегию поиска.
DFS (Depth-first Search). Например, если в качестве контейнера выбрать СТЕК, то мы реализуем алгоритм поиска в глубину. Ведь организация доступа к элементам стека такова, что мы в первую очередь будем посещать те вершины, которые попали в план последними. Посмотрим на код решения задачи
Обход в глубину:

#include <iostream>
#include <stack>
using namespace std;
int main() {
    // чтение исходных данных
    int n, v;
    cin >> n >> v;
    int matrix[n][n];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> matrix[i][j];
    stack <int> plan; // план посещения в виде стека
    plan.push(--v);   // мы нумеруем с 0, а не с 1
    matrix[v][v] = 1; // отмечаем, что эта вершина уже заносилась в план 
    int counter = 1;  // начальную уже сосчитали
    while (!plan.empty()) {
        v = plan.top(); // посещаем следующую по плану вершину 
        plan.pop();       // удаляем ее из плана посещения
        for (int u = 0; u < n; u++) { // перебираем соседние с ней
            if (matrix[v][u] and !matrix[u][u]) { // если новая, то
                plan.push(u);     // добавляем ее в план
                matrix[u][u] = 1; // отмечаем, что уже не новая
                counter++;        // считаем, сколько было вершин
            }
        }
    }
    cout << counter << endl;
}

#include <iostream>

#include <stack>

using namespace std;

int main() {

// чтение исходных данных

int n, v;

cin >> n >> v;

int matrix[n][n];

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

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

cin >> matrix[i][j];

stack <int> plan; // план посещения в виде стека

plan.push(--v); // мы нумеруем с 0, а не с 1

matrix[v][v] = 1; // отмечаем, что эта вершина уже заносилась в план

int counter = 1; // начальную уже сосчитали

while (!plan.empty()) {

v = plan.top(); // посещаем следующую по плану вершину

plan.pop(); // удаляем ее из плана посещения

for (int u = 0; u < n; u++) { // перебираем соседние с ней

if (matrix[v][u] and !matrix[u][u]) { // если новая, то

plan.push(u); // добавляем ее в план

matrix[u][u] = 1; // отмечаем, что уже не новая

counter++; // считаем, сколько было вершин

}

cout << counter << endl;

}

Единственное важное пояснение. Чтобы отметить, что вершина уже посещалась, я использую диагональ матрицы смежности графа. в условии специально подчеркнули, что там всегда нули, а значит я могу поставить matrix[v][v] = 1, чтобы обозначить вершину v как уже посещенную.

BFS (Breadth-first Search). Стоит нам немного изменить код и использовать для хранения плана ОЧЕРЕДЬ, алгоритм меняет стратегию и осуществляет поиск в ширину. Поскольку вершины будут посещаться в том порядке в котором мы их добавляли, это очень похоже на распространение волны из начальной точки. Отсюда другое название таких алгоритмов — заливки (flood) или волновые алгоритмы.

#include <iostream>
#include <queue>
using namespace std;
int main() {
    // чтение исходных данных
    int n, v;
    cin >> n >> v;
    int matrix[n][n];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> matrix[i][j];
    queue <int> plan; // план посещения в виде очереди
    plan.push(--v);   // мы нумеруем с 0, а не с 1
    matrix[v][v] = 1; // отмечаем, что эта вершина уже заносилась в план 
    int counter = 1;  // начальную уже сосчитали
    while (!plan.empty()) {
        v = plan.front(); // посещаем следующую по плану вершину 
        plan.pop();       // удаляем ее из плана посещения
        for (int u = 0; u < n; u++) { // перебираем соседние с ней
            if (matrix[v][u] and !matrix[u][u]) { // если новая, то
                plan.push(u);     // добавляем ее в план
                matrix[u][u] = 1; // отмечаем, что уже не новая
                counter++;        // считаем, сколько было вершин
            }
        }
    }
    cout << counter << endl;
}

#include <iostream>

#include <queue>

using namespace std;

int main() {

// чтение исходных данных

int n, v;

cin >> n >> v;

int matrix[n][n];

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

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

cin >> matrix[i][j];

queue <int> plan; // план посещения в виде очереди

plan.push(--v); // мы нумеруем с 0, а не с 1

matrix[v][v] = 1; // отмечаем, что эта вершина уже заносилась в план

int counter = 1; // начальную уже сосчитали

while (!plan.empty()) {

v = plan.front(); // посещаем следующую по плану вершину

plan.pop(); // удаляем ее из плана посещения

for (int u = 0; u < n; u++) { // перебираем соседние с ней

if (matrix[v][u] and !matrix[u][u]) { // если новая, то

plan.push(u); // добавляем ее в план

matrix[u][u] = 1; // отмечаем, что уже не новая

counter++; // считаем, сколько было вершин

}

cout << counter << endl;

}

Если для хранения плана написать свой контейнер или хотя бы переопределить методы GET и PUT, то вы получите новый алгоритм поиска. Например, можно извлекать вершину из плана случайным образом. В этом случае мы получим один из рандомизированных алгоритмов семейства Монте-Карло.

Задание: Найдите все четыре места, где код поиска в глубину отличается от кода поиска в ширину.
Подсказка: Если не смогди найти четвертое отличие — оно в комментариях 🙂

Related Images:

e-olymp 4852. Кратчайшее расстояние

23/05/2019 by Владимир Дроздин

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

Задача

Дан ориентированный граф. Найдите кратчайшее расстояние от вершины $x$ до всех остальных вершин графа.

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

В первой строке содержатся два натуральных числа $n$ и $x$ $(1 \leqslant n \leqslant 1000, 1 \leqslant x \leqslant n)$ — количество вершин в графе и стартовая вершина соответственно. Далее в $n$ строках по $n$ чисел — матрица смежности графа: в $i$-ой строке на $j$-ом месте стоит «$1$», если вершины $i$ и $j$ соединены ребром, и «$0$», если ребра между ними нет. На главной диагонали матрицы стоят нули.

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

Выведите через пробел числа $d_1$, $d_2$, …, $d_n$, где $d_i$ равно $-1$, если путей между $x$ и $i$ нет, в противном случае это минимальное рaсстояние между $x$ и $i$.

Тесты

#	Входные данные	Выходные данные
1	3 3 0 1 1 1 0 1 1 0 0	1 2 0
2	6 5 0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0	2 2 1 1 0 -1
3	3 1 0 0 0 0 0 1 1 1 0	0 -1 -1

Код

#include <iostream>
#include <queue>
using namespace std;
int graph[1001][1001], d[1001];
queue <int> q;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, x, v;
    cin >> n >> x;
    x--;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> graph[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        d[i] = -1;
    }
    q.push(x);
    d[x] = 0;
    while (!q.empty()) {
        v = q.front();
        q.pop();
        for (int i = 0; i < n; i++) {
            if (d[i] == -1 && graph[v][i]) {
                q.push(i);
                d[i] = d[v] + 1;
            }
        }
    } 
    for(int i = 0; i < n; i ++) {
        cout << d[i] << " ";
    }
    return 0;
}

#include <iostream>

#include <queue>

using namespace std;

int graph[1001][1001], d[1001];

queue <int> q;

int main() {

ios_base::sync_with_stdio(false);

cin.tie(NULL);

int n, x, v;

cin >> n >> x;

x--;

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

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

cin >> graph[i][j];

}

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

d[i] = -1;

}

q.push(x);

d[x] = 0;

while (!q.empty()) {

v = q.front();

q.pop();

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

if (d[i] == -1 && graph[v][i]) {

q.push(i);

d[i] = d[v] + 1;

}

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

cout << d[i] << " ";

}

return 0;

}

Решение

Данную задачу будем решать поиском в ширину. Сам граф будем хранить в двумерном массиве graph[][], в массиве d[] будем хранить кратчайшее расстояние между заданной вершиной и $i$-ой. В очереди queue <int> q будем хранить обрабатываемые вершины. В самом начале там будет хранится только наша исходная вершина, затем пока в очереди хранятся какие-либо вершины достаем верхнюю и смотрим ребра, выходящие из нее, если ранее вершины не были задействованными, то помещаем в конец очереди. Очередь опустеет, когда будут просмотрены все вершины, в которые можно попасть из исходной $x$. Сложность алгоритма $O(n)$.

Ссылки

ideone

e-olymp

Поиск в ширину на e-maxx

Related Images:

e-olymp 4853. Кратчайший путь

26/06/2018 by Андрей Лисовой

Задача

Задан неориентированный граф.
Найдите кратчайший путь от вершины $a$ до вершины $b.$

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

В первой строке находится два целых числа $n$ и $m$ $(1 \leqslant n \leqslant 50000,$ $1 \leqslant m \leqslant 100000)$ — количества вершин и рёбер соответственно. Во второй строке заданы целые числа $a$ и $b$ — стартовая и конечная вершина соответственно. Далее идут $m$ строк, описывающие рёбра.

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

Если пути между $a$ и $b$ нет, то выведите $-1.$ Иначе выведите в первой строке длину $l$ кратчайшего пути между этими двумя вершинами в рёбрах, а во второй строке выведите $l + 1$ число — вершины этого пути.

Тесты

Входные данные	Выходные данные
$4\;5$ $1\;4$ $1\;3$ $3\;2$ $2\;4$ $2\;1$ $2\;3$	$2$ $1\;2\;4$
$5\;4$ $2\;4$ $1\;2$ $2\;3$ $2\;5$ $5\;3$	$-1$
$4\;4$ $2\;3$ $2\;1$ $2\;4$ $4\;3$ $1\;3$	$2$ $2\;1\;3$
$6\;4$ $1\;6$ $1\;2$ $2\;4$ $5\;3$ $4\;5$	$-1$

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

#include <iostream>
#include <vector>
using namespace std;
 
int n,m,a,b,count = 0;
vector<vector<int> > graf; vector<int> ver; vector<int> family; bool ok = false; vector<int> ans; vector<bool> popa;
 
int bfs(int beg, int end){ // функция которая добавляет вершины в вектор вершин,которые мы просмотрим,и помечает их как уже проверенные
    count++;
    if(beg == end){
        ok = true;
        return 1;
    }else{
        for(int i = graf[beg].size() - 1;i >= 0;i--){
            if(!popa[graf[beg][i]]){
                ver.push_back(graf[beg][i]);
                family.push_back(beg);
                popa[graf[beg][i]] = true;
            }
        }
    }
    return 0;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    cin >> a >> b;
    for(int i = 0 ; i <= n; i++){ // создаем векто ввекторов
            graf.push_back(ans);
            popa.push_back(false);
    }
    ver.push_back(a);family.push_back(a);
    for(int i = 0; i < m; i++){ //в вектор вершины добавляем те вершины,с которым она связанна 
        int x,y;
        cin >> x >> y;
        if(x != y){ // проверка на петлю
            graf[x].push_back(y);
            graf[y].push_back(x);
        }
    }
    if(!graf[a].empty()){ //если вершины начала не изолированна 
        while(!ok && count < ver.size() ){ //цикл,пока мы не найдем конечную вершину,или если мы не прошли все вершины в векторе "плана"
            if(bfs(ver[count],b)){ //если мы нашли выход,то начать восстанавливать пути
                count--;// Нам надо начать с последней вершины,а это count - 1 вершина
                int p = 1; //Новая переменная,которая нужна,для нахождения первого вхождения "отца" данной вершины
                ans.push_back(b);//вектор ответа
                while(ver[count] != a){ // пока не дошли до начальной вершины
                    while(ver[p] != family[count]){//двигаемся слева пройденных по вектору вершин плана,и ищем первое вхождение вершины ОТЦА
                        p++;
                    }
                    ans.push_back(ver[p]);//добавляем в ответ вершину,из которой мы попали в предыдущую (отца)
                    count = p;// теперь ищем отца отца и так далее,пока не дойдем до начальной вершины 
                    p = 1;
                }
            }
        }
        if(ans.size() > 0){ // если вектор ответа не пуст(имеет хотябы одну вершины из пути)
            cout << ans.size()-1 << endl;
            for(int i = ans.size()-1; i >= 0; i--){
                cout << ans[i] << " "; // выводим ответ справа на лево,так сказано в условии
            }
        }else{ // иначе -1
            cout << "-1\n";
        }
    }else{//если начальная вершина изолирована,то сразу выводим -1
        cout << "-1\n";
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int n,m,a,b,count = 0;

vector<vector<int> > graf; vector<int> ver; vector<int> family; bool ok = false; vector<int> ans; vector<bool> popa;

int bfs(int beg, int end){ // функция которая добавляет вершины в вектор вершин,которые мы просмотрим,и помечает их как уже проверенные

count++;

if(beg == end){

ok = true;

return 1;

}else{

for(int i = graf[beg].size() - 1;i >= 0;i--){

if(!popa[graf[beg][i]]){

ver.push_back(graf[beg][i]);

family.push_back(beg);

popa[graf[beg][i]] = true;

}

return 0;

}

int main() {

ios::sync_with_stdio(false);

cin >> n >> m;

cin >> a >> b;

for(int i = 0 ; i <= n; i++){ // создаем векто ввекторов

graf.push_back(ans);

popa.push_back(false);

}

ver.push_back(a);family.push_back(a);

for(int i = 0; i < m; i++){ //в вектор вершины добавляем те вершины,с которым она связанна

int x,y;

cin >> x >> y;

if(x != y){ // проверка на петлю

graf[x].push_back(y);

graf[y].push_back(x);

}

if(!graf[a].empty()){ //если вершины начала не изолированна

while(!ok && count < ver.size() ){ //цикл,пока мы не найдем конечную вершину,или если мы не прошли все вершины в векторе "плана"

if(bfs(ver[count],b)){ //если мы нашли выход,то начать восстанавливать пути

count--;// Нам надо начать с последней вершины,а это count - 1 вершина

int p = 1; //Новая переменная,которая нужна,для нахождения первого вхождения "отца" данной вершины

ans.push_back(b);//вектор ответа

while(ver[count] != a){ // пока не дошли до начальной вершины

while(ver[p] != family[count]){//двигаемся слева пройденных по вектору вершин плана,и ищем первое вхождение вершины ОТЦА

p++;

}

ans.push_back(ver[p]);//добавляем в ответ вершину,из которой мы попали в предыдущую (отца)

count = p;// теперь ищем отца отца и так далее,пока не дойдем до начальной вершины

p = 1;

}

if(ans.size() > 0){ // если вектор ответа не пуст(имеет хотябы одну вершины из пути)

cout << ans.size()-1 << endl;

for(int i = ans.size()-1; i >= 0; i--){

cout << ans[i] << " "; // выводим ответ справа на лево,так сказано в условии

}

}else{ // иначе -1

cout << "-1\n";

}

}else{//если начальная вершина изолирована,то сразу выводим -1

cout << "-1\n";

}

return 0;

}

Решение задачи

Раз нам надо найти кратчайший путь, то будем использовать BFS — поиск в ширину. Мы будем постепенно просматривать вершины, внося в «план» те вершины с которыми они связанны и которые еще не внесены в «план». Для удобства используем вектора. В начале создаем вектор векторов, как бы это тавтологически не звучало, для этого я использовал вектор ответа, как объект, который добавлялся в вектор graf, выступающий в роли графа, причем мы добавляем сразу к вершинам graf[x].pushback(y);. То есть $x$-ая вершина получает связь с вершиной $y,$ и наоборот, поскольку граф неориентированный. После чего, проверяем связанна ли начальная вершина хоть с кем-нибудь, если да, то работаем циклом while, пока не наткнемся на начальную вершину, или все вершины в «плане» не будут пройдены. Если мы дошли до конечной вершины, то функция bfs вернет $1,$ что запустит тело if и мы начнем восстанавливать путь. Для этого мы заводили дополнительный вектор family в который по мере добавления в «план», также добавлялись и вершины «отцы»(откуда пришла $i$-ая вершина). Восстановленный путь записываем в вектор ans. После чего while прекращает свою работу и мы переходим к выводу результата. Если вектор ответа пуст, то выводим $-1,$ иначе выводим количество вершин, участвующих в построении пути и сам путь. Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

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:

e-olymp 4850. Шайтан-машинка

17/06/2015 by Марченко Філіп Олександрович

Условие

У Ибрагима есть магическая чёрная шайтан-машинка. На ней есть три кнопки и табло. Табло может показывать не более чем четырёхзначные числа. Каждая из кнопок меняет число некоторым образом: первая домножает его на [latex]3[/latex], вторая прибавляет к нему сумму его цифр, а третья вычитает из него [latex]2[/latex]. В случае, если число становится отрицательным или превосходит [latex]9999[/latex], шайтан-машинка ломается.

Ибрагим может нажимать кнопки в любом порядке. Его интересует, как ему получить на табло число [latex]b[/latex] после некоторой последовательности нажатий, если сейчас шайтан-машинка показывает [latex]a[/latex]. Помогите ему найти минимальное необходимое число нажатий.

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

В одной строке находится два натуральных числа [latex]a[/latex] и [latex]b[/latex] latex[/latex].

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

Вывести минимальное необходимое количество действий.

Задача
Зачтённое решение

Код

Ideone

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <iostream>

using namespace std;

int sum_n (int n){ //подсчёт суммы цифер в числе
    int res = n/1000 + (n%1000-n%100)/100 + (n%100-n%10)/10 + n%10;
    return res;
}

bool was [10000]; //массив использованных вершин.
int vertex[10000]; //подсчёт кол-ва пройденных рёбер..
queue<int> q; //очередь для BFS

//BFS
void bfs (int start, int finish){
    if (start==finish){  //если мы сразу попали в нужную вершину - выходим из программы.
        cout << 0 << endl;
        return;
    }
    else {
        for (int i=0; i<10000; i++){ //предположим, что расстояние до любой вершины = 1
            vertex[i]=1;
        }
        q.push (start); //будем рассматривать каждую вершину
        was[start] = true;
        while (!q.empty()){
            int tmp = q.front(); //рассматриваемая вершина
            q.pop();
            int tmp1 = tmp;
            tmp1 *= 3; //"ребёнок" рассматриваемой вершины, со значением родителбской вершины *3.
            if (!was[tmp1]){
                if (tmp1 == finish){//если финиш, то выводим длину пути до вершины.
                    cout << vertex[tmp] << endl;
                    return;
                }
                else if (tmp1 < 10000 && tmp1>=0){
                    was[tmp1] = true;//иначе помечаем вершину, как пройденную и засовываем её в очередь на рассмотрение
                    q.push(tmp1);
                    vertex[tmp1]=vertex[tmp]+1;//и прибавляем 1 к длине пути.
                }
            }
            //действия повторяются для других операций.
            tmp1=tmp;
            tmp1 += sum_n(tmp1);
            if (!was[tmp1]){
                if (tmp1 == finish){
                    cout << vertex[tmp] << endl;
                    return;
                }
                else if (tmp1 < 10000 && tmp1>=0){
                    was[tmp1] = true;
                    vertex[tmp1]=vertex[tmp]+1;
                    q.push(tmp1);
                }
            }
            tmp1=tmp;
            tmp1 -= 2;
            if (!was[tmp1]){
                if (tmp1 == finish){
                    cout << vertex[tmp] << endl;
                    return;
                }
                else if (tmp1 < 10000 && tmp1>=0){
                    was[tmp1] = true;
                    vertex[tmp1]=vertex[tmp]+1;
                    q.push(tmp1);
                }
            }
        }
    }
}

int main() {
    int a, b;
    cin >> a >> b; //ввод начала и конца
    bfs (a, b);//процедура выполнения
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <iostream>

using namespace std;

int sum_n (int n){ //подсчёт суммы цифер в числе

int res = n/1000 + (n%1000-n%100)/100 + (n%100-n%10)/10 + n%10;

return res;

}

bool was [10000]; //массив использованных вершин.

int vertex[10000]; //подсчёт кол-ва пройденных рёбер..

queue<int> q; //очередь для BFS

//BFS

void bfs (int start, int finish){

if (start==finish){ //если мы сразу попали в нужную вершину - выходим из программы.

cout << 0 << endl;

return;

}

else {

for (int i=0; i<10000; i++){ //предположим, что расстояние до любой вершины = 1

vertex[i]=1;

}

q.push (start); //будем рассматривать каждую вершину

was[start] = true;

while (!q.empty()){

int tmp = q.front(); //рассматриваемая вершина

q.pop();

int tmp1 = tmp;

tmp1 *= 3; //"ребёнок" рассматриваемой вершины, со значением родителбской вершины *3.

if (!was[tmp1]){

if (tmp1 == finish){//если финиш, то выводим длину пути до вершины.

cout << vertex[tmp] << endl;

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;//иначе помечаем вершину, как пройденную и засовываем её в очередь на рассмотрение

q.push(tmp1);

vertex[tmp1]=vertex[tmp]+1;//и прибавляем 1 к длине пути.

}

//действия повторяются для других операций.

tmp1=tmp;

tmp1 += sum_n(tmp1);

if (!was[tmp1]){

if (tmp1 == finish){

cout << vertex[tmp] << endl;

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;

vertex[tmp1]=vertex[tmp]+1;

q.push(tmp1);

}

tmp1=tmp;

tmp1 -= 2;

if (!was[tmp1]){

if (tmp1 == finish){

cout << vertex[tmp] << endl;

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;

vertex[tmp1]=vertex[tmp]+1;

q.push(tmp1);

}

int main() {

int a, b;

cin >> a >> b; //ввод начала и конца

bfs (a, b);//процедура выполнения

return 0;

}

Код на Java:

import java.util.*;
import java.lang.*;
import java.io.*;

class ShaitanEngines {
    private static int N = 10001;
    private static boolean [] was = new boolean [N];
    private static int [] vertice = new int [N];
    private static Queue <Integer> q = new LinkedList();
    public static int sum (int n) {
        return (n/1000 + (n%1000-n%100)/100 + (n%100-n%10)/10 + n%10);  
    }
    public static void bfs (int start, int finish) {
        if (start == finish) {
            System.out.println(1);
            return;
        }
        else {
            for (int i=0; i<N; i++){ //предположим, что расстояние до любой вершины = 1
                vertice[i]=1;
            }
            q.add (start); //будем рассматривать каждую вершину
            was[start] = true;
            while (!q.isEmpty()){
                int tmp = q.element(); //рассматриваемая вершина
                q.remove();
                int tmp1 = tmp;
                tmp1 *= 3; //"ребёнок" рассматриваемой вершины, со значением родителбской вершины *3.
                if (!was[tmp1]){
                    if (tmp1 == finish){//если финиш, то выводим длину пути до вершины.
                        System.out.println(vertice[tmp]);
                        return;
                    }
                    else if (tmp1 < 10000 && tmp1>=0){
                        was[tmp1] = true;//иначе помечаем вершину, как пройденную и засовываем её в очередь на рассмотрение
                        q.add(tmp1);
                        vertice[tmp1]=vertice[tmp]+1;//и прибавляем 1 к длине пути.
                    }
                }
                //действия повторяются для других операций.
                tmp1=tmp;
                tmp1 += sum(tmp1);
                if (!was[tmp1]){
                    if (tmp1 == finish){
                        System.out.println(vertice[tmp]);
                        return;
                    }
                    else if (tmp1 < 10000 && tmp1>=0){
                        was[tmp1] = true;
                        vertice[tmp1]=vertice[tmp]+1;
                        q.add(tmp1);
                    }
                }
                tmp1=tmp;
                tmp1 -= 2;
                if (!was[tmp1]){
                    if (tmp1 == finish){
                        System.out.println(vertice[tmp]);
                        return;
                    }
                    else if (tmp1 < 10000 && tmp1>=0){
                        was[tmp1] = true;
                        vertice[tmp1]=vertice[tmp]+1;
                        q.add(tmp1);
                    }
                }
            }
        }
    }
    public static void main (String[] args) {
        Scanner sc = new Scanner (System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        bfs(a, b);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class ShaitanEngines {

private static int N = 10001;

private static boolean [] was = new boolean [N];

private static int [] vertice = new int [N];

private static Queue <Integer> q = new LinkedList();

public static int sum (int n) {

return (n/1000 + (n%1000-n%100)/100 + (n%100-n%10)/10 + n%10);

}

public static void bfs (int start, int finish) {

if (start == finish) {

System.out.println(1);

return;

}

else {

for (int i=0; i<N; i++){ //предположим, что расстояние до любой вершины = 1

vertice[i]=1;

}

q.add (start); //будем рассматривать каждую вершину

was[start] = true;

while (!q.isEmpty()){

int tmp = q.element(); //рассматриваемая вершина

q.remove();

int tmp1 = tmp;

tmp1 *= 3; //"ребёнок" рассматриваемой вершины, со значением родителбской вершины *3.

if (!was[tmp1]){

if (tmp1 == finish){//если финиш, то выводим длину пути до вершины.

System.out.println(vertice[tmp]);

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;//иначе помечаем вершину, как пройденную и засовываем её в очередь на рассмотрение

q.add(tmp1);

vertice[tmp1]=vertice[tmp]+1;//и прибавляем 1 к длине пути.

}

//действия повторяются для других операций.

tmp1=tmp;

tmp1 += sum(tmp1);

if (!was[tmp1]){

if (tmp1 == finish){

System.out.println(vertice[tmp]);

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;

vertice[tmp1]=vertice[tmp]+1;

q.add(tmp1);

}

tmp1=tmp;

tmp1 -= 2;

if (!was[tmp1]){

if (tmp1 == finish){

System.out.println(vertice[tmp]);

return;

}

else if (tmp1 < 10000 && tmp1>=0){

was[tmp1] = true;

vertice[tmp1]=vertice[tmp]+1;

q.add(tmp1);

}

public static void main (String[] args) {

Scanner sc = new Scanner (System.in);

int a = sc.nextInt();

int b = sc.nextInt();

bfs(a, b);

}

Решение

Для решения данной задачи я решил использовать алгоритм BFS (поиск в ширину). Обычно, данный алгоритм применяется для поиска пути от одной вершины к другой, причём длина пути должна быть минимальной.

Всю «карту» расположения операций можно представить в виде графа-дерева, где от каждой вершины отходят максимум 3 ребра (в каждой вершине по операции, проделанной со значением вершины, которая находится на уровень выше). Будем рассматривать каждую вершину. Если исходная вершина и есть конечной, то выходим из программы с вердиктом «0». Иначе будем поочерёдно рассматривать все вершины. Заведём массив расстояний, в котором предположим, что расстояние до нужной нам вершины равно 1. С проходом каждой вершины будем подсчитывать расстояние до нужной нам вершины (прибавляя к расстоянию 1), в которую мы рано или поздно попадём.

Related Images:

e-olymp 432. Подземелье

20/05/2015 by Царев Николай Александрович

Подземелье

Вы попали в 3D подземный лабиринт и необходимо найти быстрый выход! Карта подземелья составлена из единичных кубических комнат, по которым можно или нельзя передвигаться. Нужно всего одну минуту, чтобы переместиться она одну единицу на север, юг, восток, запад, вверх или вниз. Вы не можете двигаться по диагонали, и лабиринт окружен твердой скальной породой со всех сторон.

Можно ли выбраться из лабиринта? Если да, то какое времени это займет?

Техническое условие

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

Состоит из ряда подземелий. Каждое описание подземелья начинается со строки, содержащей три целых числа: количество уровней в подземелье l, а также r и c — количество строк и столбцов, описывающих план каждого уровня (все числа не больше 30).

Далее следует l блоков по r строк, каждая по c символов. Каждое число описывает одну ячейку подземелья. Запрещенные для перемещения кубы подземелья обозначены символом ‘#‘, а пустые клетки обозначены ‘.‘. Ваша стартовая позиция обозначается буквой ‘S‘, а выход буквой ‘Е‘. Все описания подземелий отделены пустой строкой. Описание входных данных заканчивается тремя нулями.

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

Для каждого лабиринта необходимо вывести одну строку. Если есть возможность добраться до выхода, вывести строку вида

Escaped in X minute(s).

где X — наименьшее время, необходимое для достижения выхода.

Если достичь выход невозможно, вывести строку

Trapped!

ТЕСТЫ:

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

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

3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0

3 4 5

S....

.###.

.##..

###.#

#####

##.##

##...

#####

#.###

####E

1 3 3

S##

#E#

###

0 0 0

Escaped in 11 minute(s).
Trapped!

1 2	Escaped in 11 minute(s). Trapped!

Тесты взяты с сайта e-olimp. Подтверждение прохождения задачи на e-olimp.

Задача на E-Olimp!

#include <iostream>

using namespace std;

struct node{
   int x,y,z;
   node *prev;
   node (int x0, int y0, int z0,  node* las) { x = x0; y=y0; z=z0;  prev = las;}
   node();
};  //Структура "Узел" используемая в структуре "Очередь"

struct quene{ //Структура "Очередь"
   int k=0;
   node *last=NULL;
   node *first=NULL;
   node *tmp=NULL;

   void push( int n, int m, int g){
       node* x = new node(n,m,g, NULL);
       k++;
       if(k!=1)
           last->prev = x;
       last = x;
       if(k==1)
           first=x;
   }
   
   void pop(){
       tmp=first;
       first=first->prev;
       delete tmp;
       k--;
       }

};



int main()
{
   int l,r,c;
   cin >> l >> r >> c;
   while((l!=0)&&(r!=0)&&(c!=0)){ //Внешний цикл
   int mas[l+2][r+2][c+2];
   bool masb[l+2][r+2][c+2];
   char u;
   int st1,st2,st3;
   int fs1,fs2,fs3;
   for(int i1=0; i1<l+2; i1++){ //Начало считывания и обработки данных
       for(int i2=0; i2<r+2; i2++){
           for(int i3=0; i3<c+2; i3++){
               masb[i1][i2][i3]=0;
               if((i1==0)||(i2==0)||(i3==0)||(i1==l+1)||(i2==r+1)||(i3==c+1))
                   mas[i1][i2][i3]=-1;
               else{
               cin>>u;
               if(u=='#'){
               mas[i1][i2][i3]=-1;}
               if(u=='.'){
                   mas[i1][i2][i3]=0;
               }
               if(u=='S'){
                   mas[i1][i2][i3]=0;
                   st1=i1;st2=i2;st3=i3;
               }
               if(u=='E'){
                   mas[i1][i2][i3]=0;
                   fs1=i1;fs2=i2;fs3=i3;
               }
               }
           }
           }
       } // Конец обработки

   quene ts; //Создание очереди
   ts.push(st1,st2,st3);// Кладем в нее "стартовую" вершину
   while(ts.k!=0){  //Запускаем поиск
       int x1=ts.first->x;
       int y1=ts.first->y;
       int z1=ts.first->z;  //Для удобства сохраняем координаты 
       //обрабатываемой вершины в специальных переменных

       if(mas[x1+1][y1][z1]>=0){ // Вершина справа
           if(mas[x1+1][y1][z1]!=0)
               mas[x1+1][y1][z1]=min(mas[x1+1][y1][z1],mas[x1][y1][z1]+1);
           else
               mas[x1+1][y1][z1]=mas[x1][y1][z1]+1;
           if(masb[x1+1][y1][z1]==0){
               masb[x1+1][y1][z1]=1;
               ts.push(x1+1,y1,z1);
           }
       }

       if(mas[x1-1][y1][z1]>=0){ //Вершина слева
           if(mas[x1-1][y1][z1]!=0)
               mas[x1-1][y1][z1]=min(mas[x1-1][y1][z1],mas[x1][y1][z1]+1);
           else
               mas[x1-1][y1][z1]=mas[x1][y1][z1]+1;
           if(masb[x1-1][y1][z1]==0){
               masb[x1-1][y1][z1]=1;
               ts.push(x1-1,y1,z1);
           }
       }

       if(mas[x1][y1+1][z1]>=0){ //Вершина вверху
           if(mas[x1][y1+1][z1]!=0)
               mas[x1][y1+1][z1]=min(mas[x1][y1+1][z1],mas[x1][y1][z1]+1);
           else
               mas[x1][y1+1][z1]=mas[x1][y1][z1]+1;
           if(masb[x1][y1+1][z1]==0){
               masb[x1][y1+1][z1]=1;
               ts.push(x1,y1+1,z1);
           }
       }

       if(mas[x1][y1-1][z1]>=0){ //Вершина внизу
           if(mas[x1][y1-1][z1]!=0)
               mas[x1][y1-1][z1]=min(mas[x1][y1-1][z1],mas[x1][y1][z1]+1);
           else
               mas[x1][y1-1][z1]=mas[x1][y1][z1]+1;
           if(masb[x1][y1-1][z1]==0){
               masb[x1][y1-1][z1]=1;
               ts.push(x1,y1-1,z1);
           }
       }

       if(mas[x1][y1][z1+1]>=0){ //Вершина на уровень выше
           if(mas[x1][y1][z1+1]!=0)
               mas[x1][y1][z1+1]=min(mas[x1][y1][z1+1],mas[x1][y1][z1]+1);
           else
               mas[x1][y1][z1+1]=mas[x1][y1][z1]+1;
           if(masb[x1][y1][z1+1]==0){
               masb[x1][y1][z1+1]=1;
               ts.push(x1,y1,z1+1);
           }
       }

       if(mas[x1][y1][z1-1]>=0){ //Вершина на уровень ниже
           if(mas[x1][y1][z1-1]!=0)
               mas[x1][y1][z1-1]=min(mas[x1][y1][z1-1],mas[x1][y1][z1]+1);
           else
               mas[x1][y1][z1-1]=mas[x1][y1][z1]+1;
           if(masb[x1][y1][z1-1]==0){
               masb[x1][y1][z1-1]=1;
               ts.push(x1,y1,z1-1);
           }
       }
       ts.pop(); //Удаление обработанной вершины из очереди

       }
       if(mas[fs1][fs2][fs3]!=0) // Последняя проверка результата
       cout <<"Escaped in " << mas[fs1][fs2][fs3] << " minute(s)."<< endl;
       else
       cout << "Trapped!" << endl;
       cin >> l >> r >> c; // Считывание чисел для внешнего цикла
       }
   return 0;

}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

#include <iostream>

using namespace std;

struct node{

int x,y,z;

node *prev;

node (int x0, int y0, int z0, node* las) { x = x0; y=y0; z=z0; prev = las;}

node();

}; //Структура "Узел" используемая в структуре "Очередь"

struct quene{ //Структура "Очередь"

int k=0;

node *last=NULL;

node *first=NULL;

node *tmp=NULL;

void push( int n, int m, int g){

node* x = new node(n,m,g, NULL);

k++;

if(k!=1)

last->prev = x;

last = x;

if(k==1)

first=x;

}

void pop(){

tmp=first;

first=first->prev;

delete tmp;

k--;

}

};

int main()

{

int l,r,c;

cin >> l >> r >> c;

while((l!=0)&&(r!=0)&&(c!=0)){ //Внешний цикл

int mas[l+2][r+2][c+2];

bool masb[l+2][r+2][c+2];

char u;

int st1,st2,st3;

int fs1,fs2,fs3;

for(int i1=0; i1<l+2; i1++){ //Начало считывания и обработки данных

for(int i2=0; i2<r+2; i2++){

for(int i3=0; i3<c+2; i3++){

masb[i1][i2][i3]=0;

if((i1==0)||(i2==0)||(i3==0)||(i1==l+1)||(i2==r+1)||(i3==c+1))

mas[i1][i2][i3]=-1;

else{

cin>>u;

if(u=='#'){

mas[i1][i2][i3]=-1;}

if(u=='.'){

mas[i1][i2][i3]=0;

}

if(u=='S'){

mas[i1][i2][i3]=0;

st1=i1;st2=i2;st3=i3;

}

if(u=='E'){

mas[i1][i2][i3]=0;

fs1=i1;fs2=i2;fs3=i3;

}

} // Конец обработки

quene ts; //Создание очереди

ts.push(st1,st2,st3);// Кладем в нее "стартовую" вершину

while(ts.k!=0){ //Запускаем поиск

int x1=ts.first->x;

int y1=ts.first->y;

int z1=ts.first->z; //Для удобства сохраняем координаты

//обрабатываемой вершины в специальных переменных

if(mas[x1+1][y1][z1]>=0){ // Вершина справа

if(mas[x1+1][y1][z1]!=0)

mas[x1+1][y1][z1]=min(mas[x1+1][y1][z1],mas[x1][y1][z1]+1);

else

mas[x1+1][y1][z1]=mas[x1][y1][z1]+1;

if(masb[x1+1][y1][z1]==0){

masb[x1+1][y1][z1]=1;

ts.push(x1+1,y1,z1);

}

if(mas[x1-1][y1][z1]>=0){ //Вершина слева

if(mas[x1-1][y1][z1]!=0)

mas[x1-1][y1][z1]=min(mas[x1-1][y1][z1],mas[x1][y1][z1]+1);

else

mas[x1-1][y1][z1]=mas[x1][y1][z1]+1;

if(masb[x1-1][y1][z1]==0){

masb[x1-1][y1][z1]=1;

ts.push(x1-1,y1,z1);

}

if(mas[x1][y1+1][z1]>=0){ //Вершина вверху

if(mas[x1][y1+1][z1]!=0)

mas[x1][y1+1][z1]=min(mas[x1][y1+1][z1],mas[x1][y1][z1]+1);

else

mas[x1][y1+1][z1]=mas[x1][y1][z1]+1;

if(masb[x1][y1+1][z1]==0){

masb[x1][y1+1][z1]=1;

ts.push(x1,y1+1,z1);

}

if(mas[x1][y1-1][z1]>=0){ //Вершина внизу

if(mas[x1][y1-1][z1]!=0)

mas[x1][y1-1][z1]=min(mas[x1][y1-1][z1],mas[x1][y1][z1]+1);

else

mas[x1][y1-1][z1]=mas[x1][y1][z1]+1;

if(masb[x1][y1-1][z1]==0){

masb[x1][y1-1][z1]=1;

ts.push(x1,y1-1,z1);

}

if(mas[x1][y1][z1+1]>=0){ //Вершина на уровень выше

if(mas[x1][y1][z1+1]!=0)

mas[x1][y1][z1+1]=min(mas[x1][y1][z1+1],mas[x1][y1][z1]+1);

else

mas[x1][y1][z1+1]=mas[x1][y1][z1]+1;

if(masb[x1][y1][z1+1]==0){

masb[x1][y1][z1+1]=1;

ts.push(x1,y1,z1+1);

}

if(mas[x1][y1][z1-1]>=0){ //Вершина на уровень ниже

if(mas[x1][y1][z1-1]!=0)

mas[x1][y1][z1-1]=min(mas[x1][y1][z1-1],mas[x1][y1][z1]+1);

else

mas[x1][y1][z1-1]=mas[x1][y1][z1]+1;

if(masb[x1][y1][z1-1]==0){

masb[x1][y1][z1-1]=1;

ts.push(x1,y1,z1-1);

}

ts.pop(); //Удаление обработанной вершины из очереди

}

if(mas[fs1][fs2][fs3]!=0) // Последняя проверка результата

cout <<"Escaped in " << mas[fs1][fs2][fs3] << " minute(s)."<< endl;

else

cout << "Trapped!" << endl;

cin >> l >> r >> c; // Считывание чисел для внешнего цикла

}

return 0;

}

ССЫЛКА НА IDEONE.COM

(Программа также проверенна в Code::Blocks)

Алгоритм решения:

Основа всего алгоритма — поиск в ширину, реализованный на трехмерном массиве. Для реализации я использовал собственную структуру очереди. В двух словах идея такова:
1) Считываем данные, заполняя массив по принципу: Если «комната закрыта» — ставим -1. Если открыта — ставим ноль. Старт и Финиш также заполняем нулями, но запоминаем их координаты.

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

2) Реализация самого поиска. Создаем очередь и помещаем в нее стартовую вершину. Затем запускаем цикл до тех пор, пока очередь не пуста.

3) Действия в цикле повторяются шесть раз, на каждое из возможных направлений.

Проверяем закрыта ли эта комната ( проверка на положительное число)
Если комната открыта, проверяем, есть ли в ней уже какое то время. Если да, то кладем в нее минимум из времени пути который был уже проложен, и проложен сейчас. В противном случае, кладем в нее время данного пути.
Проверяем, была ли посещена эта комната ранее. В противном случае — отмечаем что она посещалась и добавляем ее в очередь.

4) Извлекаем вершину из очереди.

В итоге мы получаем такой же трехмерный массив, в котором каждая клетка отмечена минимальным временем от старта. Так как расположение финиша мы запомнили, просто проверяем его «вес». В зависимости от результата проверки выводим требуемый по условию результат.

Примечание!

1)Для удобной реализации поиска, оба массива создаем на два уровня больше, как бы делая ему рамку ( маску).

2) Поскольку в одном тесте идет не один набор уровней, программа выполняется в цикле, который работает до тех пор, пока не получит в качестве трех чисел — три нуля. ( В комментариях назовем этот цикл «внешним»)

Related Images:

e-olymp 1061. Покраска лабиринта

19/05/2015 by Сорокина Полина

Задача e-olimp 1061.

Лабиринт представляет собой квадрат, состоящий из N×N сегментов. Каждый из сегментов может быть либо пустым, либо заполненным камнем. Гарантируется, что левый верхний и правый нижний сегменты пусты. Лабиринт обнесен снизу, сверху, слева и справа стенами, оставляющими свободными только левый верхний и правый нижний углы. Директор лабиринта решил покрасить стены лабиринта, видимые изнутри. Помогите ему рассчитать количество краски, необходимой для этого.

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

В первой строке находится число N, затем идут N строк по N символов: точка обозначает пустой сегмент, решетка — сегмент со стеной.

3 ≤ N ≤ 33, размер сегмента 3×3, высота стен 3 метра.

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

Вывести одно число — площадь видимой части внутренних стен лабиринта в квадратных метрах.

Пример

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

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

. . . . .

. . . # #

. . # . .

. . # # #

. . . . .

198

C++:

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

int check(int row, int col, char** lab, int** visited, queue<int>& plan){//находим количество стен рядом с каждой клеткой
	int empty = 0;//пустые клетки
	if(!visited[row][col]){
			if(lab[row+1][col]=='.'){//проверяем нижнюю клетку
				empty++;
				if(!visited[row+1][col]){
					plan.push(row+1);
					plan.push(col);
				}
			}
			if(lab[row-1][col]=='.'){//проверяем верхнюю клетку
				empty++;
				if(!visited[row-1][col]){
					plan.push(row-1);
					plan.push(col);
				}
			}
			if(lab[row][col+1]=='.'){//проверяем правую клетку
				empty++;
				if(!visited[row][col+1]){
					plan.push(row);
					plan.push(col+1);
				}
			}
			if(lab[row][col-1]=='.'){//проверяем левую клетку
				empty++;
				if(!visited[row][col-1]){
					plan.push(row);
					plan.push(col-1);
				}
			}
			visited[row][col]=1;//отмечаем, что клетка пройдена
			return 4-empty;//количество стен рядом с клеткой
	}
	return 0;
}

int main() {
	int N;
	cin >> N;
	char** lab = new char* [N+2];
	int** visited = new int * [N+2];
	for(int i=0; i<N+2; i++){
		lab[i] = new char [N+2];
		visited[i] = new int [N+2];
		for(int j=0; j<N+2; j++){
			visited[i][j] = 0;//массив для проверки посещённости клеток
			if(i==0||i==N+1||j==0||j==N+1){
				lab[i][j]='*';//вокруг данного лабиринта делаем стену
			} else {
				cin >> lab[i][j];//данный лабиринт
			}
		}
	}
	queue <int> plan;
	plan.push(1);//начинаем считать с левой верхней клетки
	plan.push(1);
	int walls=0;
	while(!plan.empty()){
		int row=plan.front();
		plan.pop();
		int col=plan.front();
		plan.pop();
		walls+=check(row, col, lab, visited, plan);
	}
	if(!visited[N][N]){//если не попали в правую нижнюю клетку
		plan.push(N);//считаем начиная с неё
		plan.push(N);
		while(!plan.empty()){
			int row=plan.front();
			plan.pop();
			int col=plan.front();
			plan.pop();
			walls+=check(row, col, lab, visited, plan);
		}
	}
	walls-=4;//стены у левого верхнего и правого нижнего угла отсутствуют
	int meters=walls*9;
	cout << meters << endl;
	return 0;
}

#include <iostream>

#include <queue>

using namespace std;

int check(int row, int col, char** lab, int** visited, queue<int>& plan){//находим количество стен рядом с каждой клеткой

int empty = 0;//пустые клетки

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

if(lab[row+1][col]=='.'){//проверяем нижнюю клетку

empty++;

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

plan.push(row+1);

plan.push(col);

}

if(lab[row-1][col]=='.'){//проверяем верхнюю клетку

empty++;

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

plan.push(row-1);

plan.push(col);

}

if(lab[row][col+1]=='.'){//проверяем правую клетку

empty++;

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

plan.push(row);

plan.push(col+1);

}

if(lab[row][col-1]=='.'){//проверяем левую клетку

empty++;

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

plan.push(row);

plan.push(col-1);

}

visited[row][col]=1;//отмечаем, что клетка пройдена

return 4-empty;//количество стен рядом с клеткой

}

return 0;

}

int main() {

int N;

cin >> N;

char** lab = new char* [N+2];

int** visited = new int * [N+2];

for(int i=0; i<N+2; i++){

lab[i] = new char [N+2];

visited[i] = new int [N+2];

for(int j=0; j<N+2; j++){

visited[i][j] = 0;//массив для проверки посещённости клеток

if(i==0||i==N+1||j==0||j==N+1){

lab[i][j]='*';//вокруг данного лабиринта делаем стену

} else {

cin >> lab[i][j];//данный лабиринт

}

queue <int> plan;

plan.push(1);//начинаем считать с левой верхней клетки

plan.push(1);

int walls=0;

while(!plan.empty()){

int row=plan.front();

plan.pop();

int col=plan.front();

plan.pop();

walls+=check(row, col, lab, visited, plan);

}

if(!visited[N][N]){//если не попали в правую нижнюю клетку

plan.push(N);//считаем начиная с неё

plan.push(N);

while(!plan.empty()){

int row=plan.front();

plan.pop();

int col=plan.front();

plan.pop();

walls+=check(row, col, lab, visited, plan);

}

walls-=4;//стены у левого верхнего и правого нижнего угла отсутствуют

int meters=walls*9;

cout << meters << endl;

return 0;

}

Java:

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
	public static int check(int row, int col, char [][] lab, int [][] visited, ArrayDeque <Integer> plan){//находим количество стен рядом с каждой клеткой
		int empty = 0;//пустые клетки
		if(visited[row][col]!=1){
				if(lab[row+1][col]=='.'){//проверяем нижнюю клетку
					empty++;
					if(visited[row+1][col]!=1){
						plan.offer(row+1);
						plan.offer(col);
					}
				}
				if(lab[row-1][col]=='.'){//проверяем верхнюю клетку
					empty++;
					if(visited[row-1][col]!=1){
						plan.offer(row-1);
						plan.offer(col);
					}
				}
				if(lab[row][col+1]=='.'){//проверяем правую клетку
					empty++;
					if(visited[row][col+1]!=1){
						plan.offer(row);
						plan.offer(col+1);
					}
				}
				if(lab[row][col-1]=='.'){//проверяем левую клетку
					empty++;
					if(visited[row][col-1]!=1){
						plan.offer(row);
						plan.offer(col-1);
					}
				}
				visited[row][col]=1;//отмечаем, что клетка пройдена
				return 4-empty;//количество стен рядом с клеткой
		}
		return 0;
	}
	
	
	public static void main (String[] args)
	{
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		char [][] lab = new char [N+2][];
		int [][] visited = new int [N+2][];
		for(int i=0; i<N+2; i++){
			lab[i] = new char [N+2];
			visited[i] = new int [N+2];
			for(int j=0; j<N+2; j++){
				visited[i][j] = 0;//массив для проверки посещённости клеток
				if(i==0||i==N+1||j==0||j==N+1){
					lab[i][j]='*';//вокруг данного лабиринта делаем стену
				}
			}
		}
		String line;
		for(int i=1; i<N+1; i++){
			line = in.next();
			for(int j=1; j<N+1; j++){
				lab[i][j]=line.charAt(j-1);//заполняем лабиринт
			}
		}
		
		ArrayDeque <Integer> plan = new ArrayDeque<Integer>();
		plan.offer(1);//начинаем считать с левой верхней клетки
		plan.offer(1);
		int walls=0;
		while(!plan.isEmpty()){
			int row=plan.poll();
			int col=plan.poll();
			walls+=check(row, col, lab, visited, plan);
		}
		if(visited[N][N]!=1){//если не попали в правую нижнюю клетку
			plan.offer(N);//считаем начиная с неё
			plan.offer(N);
			while(!plan.isEmpty()){
				int row=plan.poll();
				int col=plan.poll();
				walls+=check(row, col, lab, visited, plan);
			}
		}
		walls-=4;//стены у левого верхнего и правого нижнего угла отсутствуют
		int meters = walls * 9;
		System.out.println(meters);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static int check(int row, int col, char [][] lab, int [][] visited, ArrayDeque <Integer> plan){//находим количество стен рядом с каждой клеткой

int empty = 0;//пустые клетки

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

if(lab[row+1][col]=='.'){//проверяем нижнюю клетку

empty++;

if(visited[row+1][col]!=1){

plan.offer(row+1);

plan.offer(col);

}

if(lab[row-1][col]=='.'){//проверяем верхнюю клетку

empty++;

if(visited[row-1][col]!=1){

plan.offer(row-1);

plan.offer(col);

}

if(lab[row][col+1]=='.'){//проверяем правую клетку

empty++;

if(visited[row][col+1]!=1){

plan.offer(row);

plan.offer(col+1);

}

if(lab[row][col-1]=='.'){//проверяем левую клетку

empty++;

if(visited[row][col-1]!=1){

plan.offer(row);

plan.offer(col-1);

}

visited[row][col]=1;//отмечаем, что клетка пройдена

return 4-empty;//количество стен рядом с клеткой

}

return 0;

}

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

int N = in.nextInt();

char [][] lab = new char [N+2][];

int [][] visited = new int [N+2][];

for(int i=0; i<N+2; i++){

lab[i] = new char [N+2];

visited[i] = new int [N+2];

for(int j=0; j<N+2; j++){

visited[i][j] = 0;//массив для проверки посещённости клеток

if(i==0||i==N+1||j==0||j==N+1){

lab[i][j]='*';//вокруг данного лабиринта делаем стену

}

String line;

for(int i=1; i<N+1; i++){

line = in.next();

for(int j=1; j<N+1; j++){

lab[i][j]=line.charAt(j-1);//заполняем лабиринт

}

ArrayDeque <Integer> plan = new ArrayDeque<Integer>();

plan.offer(1);//начинаем считать с левой верхней клетки

plan.offer(1);

int walls=0;

while(!plan.isEmpty()){

int row=plan.poll();

int col=plan.poll();

walls+=check(row, col, lab, visited, plan);

}

if(visited[N][N]!=1){//если не попали в правую нижнюю клетку

plan.offer(N);//считаем начиная с неё

plan.offer(N);

while(!plan.isEmpty()){

int row=plan.poll();

int col=plan.poll();

walls+=check(row, col, lab, visited, plan);

}

walls-=4;//стены у левого верхнего и правого нижнего угла отсутствуют

int meters = walls * 9;

System.out.println(meters);

}

Для решения задачи я использовала алгоритм поиска в ширину: начиная с левой верхней клетки, которая гарантированно пуста, проверяю все смежные с ней и заношу их в план проверки. Для каждой клетки считаю количество пустых смежных клеток и получаю число стен рядом с ней. Чтобы было удобно проверять смежные клетки на пустоту, я сделала «стену» вокруг данного лабиринта. После проверки клетки отмечаю, что она просмотрена.

Так как в условии не гарантируется, что есть проход от левой верхней до правой нижней клетки, проверяю, посещена ли последняя. Если нет, снова запускаю поиск, начиная с неё.

Засчитанное решение.

Задача на Ideone:
C++
Java