1

Всем привет ,есть задача ! Как решить мне ёё ? Можете сказать алгоритм ?

Пастух Боран не боится оставить своего барана щепать траву в любом месте каменистого поля. Он уверен, что баран всегда найдет самый короткий путь к своему хозяину. Поле, где пасется баран, можно представить прямоугольником, разделенном на квадратные участки со стороной 1 метр. Этот участок или свободный от камней или на нем расположены камни, на которые баран не сумеет забраться. Баран находится на самом левом нижним участке, а Боран на самом правом верхнем участке. Баран может переходить с одного участка на любой соседний участок, если он не занят камнями. А вы сумеете узнать длину самого короткого пути барана к своему хозяину?

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

В первой строке заданы два натуральных числа N и M (1 <= N, M < 500) – размеры поля (количество строк и столбцов участков поля). В следующих N строках заданы через один пробел M чисел 0 или 1: 0 означает, что соответствующий участок свободен, 1 означает, что на участке находятся камни.

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

Одно число – длина кратчайшего пути барана к своему хозяину.

Пример входных данных

6 6
1 1 0 0 1 0
1 0 0 1 1 0
0 1 0 0 0 1
1 1 0 1 1 1
1 1 1 0 1 1
0 0 0 0 1 1

Пример выходных данных

8
6
  • 2
    Поиск в ширину? Если длины рёбер графа равны между собой, поиск в ширину является оптимальным, то есть всегда находит кратчайший путь.
    – Harry
    Commented 9 апр. 2017 в 10:15
  • А можете на псевдо коде показать @Harry? Не вник Commented 9 апр. 2017 в 10:20
  • Сейчас - нет, должен убегать на часик-другой... Да гляньте по ссылке, или просто поищите в Интернете. Об этом - полно рассказывается...
    – Harry
    Commented 9 апр. 2017 в 10:22
  • A*
    – vp_arth
    Commented 9 апр. 2017 в 10:31
  • Гляньте тут.
    – user207618
    Commented 9 апр. 2017 в 10:38

2 ответа 2

3

Вашу задачу можно свести к более частной. Такой задачей будет поиск пути. Существует множество алгоритмов решения это задачи.

Вот некотрые из них:

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

Алгоритм Дейкстры. Данный алгоритм находит длину пути от любой вершины графа(в вашем случае матрицы), до всех остальных. В статье по ссылке он подробно описывается, также есть блоксхема и псевдокод.

Алгоритм A*. Очень хороший алгоритм который можно подстроить под практически любую задачу.

3
  • дополнил ещё несколько алгоритмов к ответу. Commented 9 апр. 2017 в 11:48
  • @ИльяЧижанов A* конечно хорош, но он все таки предназначен для поиска пути, нам же нужна лишь его длина. Тем более для освоения новичком, я считаю, он будет сложен
    – sm4ll_3gg
    Commented 9 апр. 2017 в 11:58
  • @sm4ll-3gg полностью согласен о его сложности, но не упомянуть его было бы преступлением. Все эти алгоритмы делают примерно одно и то же, но только по разному, включая алгоритм Дейкстры. Для определения длины нам нужен путь. Commented 9 апр. 2017 в 12:18
2

Ну что там сложного? вот, на коленке, дословный (не оптимизированный) перевод описания из книжки "Алгоритмы. Просто, как 2x2" -

#include <vector>
#include <iostream>
#include <iomanip>
#include <limits>
#include <queue>

using namespace std;

struct vertex
{
    unsigned int r, c;
    int value = 0;
    int color = 0; // white; 1 - gray, 2 - black
    int dist  = numeric_limits<int>::max();
};

vector<vector<vertex>> mx;

int main()
{
    unsigned int N, M;
    cin >> N >> M;
    mx = vector<vector<vertex>>(N,vector<vertex>(M));
    for(unsigned int r = 0; r < N; ++r)
        for(unsigned int c = 0; c < M; ++c)
        {
            mx[r][c].r = r;
            mx[r][c].c = c;
            cin >> mx[r][c].value;
        }
    mx[N-1][0].dist  = 0;
    mx[N-1][0].color = 1;
    // begin: (N-1,0) end: (0,N-1)

    queue<vertex*> Q;
    Q.push(&mx[N-1][0]);
    while(!Q.empty())
    {
        vertex* u = Q.front();
        Q.pop();
        if (u->r == 0 && u->c == M-1)
        {
            cout << u->dist << endl;
            return 0;
        }
        for(int dr = -1; dr <= 1; ++dr)
        {
            int r = u->r + dr;
            if (r < 0 || r >= N) continue;
            for(int dc = -1; dc <= 1; ++dc)
            {
                if (dr == 0 && dc == 0) continue;
                int c = u->c + dc;
                if (c < 0 || c >= M) continue;
                if (mx[r][c].value == 1) continue;
                if (mx[r][c].color != 0) continue;

                mx[r][c].color = 1;
                mx[r][c].dist = u->dist + 1;
                Q.push(&mx[r][c]);

            }
        }
        u->color = 2;
    }
}

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.