Рубрики

Кратчайший путь в двоичном лабиринте

Учитывая матрицу MxN, где каждый элемент может быть 0 или 1. Нам нужно найти кратчайший путь между данной исходной ячейкой и целевой ячейкой. Путь может быть создан только из ячейки, если его значение равно 1.

Ожидаемая сложность времени O (MN).

Например —

Input:
mat[ROW][COL]  = {{1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
                  {1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },
                  {1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
                  {0, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
                  {1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },
                  {1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },
                  {1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
                  {1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
                  {1, 1, 0, 0, 0, 0, 1, 0, 0, 1 }};
Source = {0, 0};
Destination = {3, 4};

Output:
Shortest Path is 11 

Идея основана на алгоритме Ли и использует BFS.

  1. Мы начинаем с исходной ячейки и вызываем процедуру BFS.
  2. Мы поддерживаем очередь для хранения координат матрицы и инициализируем ее исходной ячейкой.
  3. Мы также поддерживаем посещаемый логический массив того же размера, что и наша входная матрица, и инициализируем все его элементы как false.
    1. Мы петли, пока очередь не пуста
    2. Снять переднюю ячейку из очереди
    3. Вернитесь, если достигнуты координаты пункта назначения.
    4. Для каждой из четырех смежных ячеек, если значение равно 1 и они еще не посещены, мы ставим его в очередь и также помечаем как посещенные.

Обратите внимание, что BFS работает здесь, потому что он не учитывает один путь сразу. Он учитывает все пути, начиная с источника, и продвигается вперед на одну единицу по всем этим путям одновременно, что гарантирует, что при первом посещении пункта назначения это самый короткий путь.

Ниже приведена реализация идеи —

C ++

// C ++ программа для поиска кратчайшего пути между
// указанная исходная ячейка для целевой ячейки.
#include <bits/stdc++.h>

using namespace std;

#define ROW 9
#define COL 10

  
// Для хранения матричных клеточных кординатов

struct Point

{

    int x;

    int y;

};

  
// Структура данных для очереди, используемой в BFS

struct queueNode

{

    Point pt;  // Кординаты клетки

    int dist;  // расстояние ячейки от источника

};

  
// проверяем, является ли данная ячейка (строка, столбец) допустимой
// ячейка или нет.

bool isValid(int row, int col)

{

    // возвращаем true если номер строки и номер столбца

    // находится в диапазоне

    return (row >= 0) && (row < ROW) &&

           (col >= 0) && (col < COL);

}

  
// Эти массивы используются для получения строки и столбца
// номера 4 соседей данной ячейки

int rowNum[] = {-1, 0, 0, 1};

int colNum[] = {0, -1, 1, 0};

  
// функция, чтобы найти кратчайший путь между
// указанная исходная ячейка для целевой ячейки.

int BFS(int mat[][COL], Point src, Point dest)

{

    // проверка исходной и целевой ячейки

    // матрицы имеют значение 1

    if (!mat[src.x][src.y] || !mat[dest.x][dest.y])

        return -1;

  

    bool visited[ROW][COL];

    memset(visited, false, sizeof visited);

      

    // Пометить исходную ячейку как посещенную

    visited[src.x][src.y] = true;

  

    // Создать очередь для BFS

    queue<queueNode> q;

      

    // Расстояние исходной ячейки равно 0

    queueNode s = {src, 0};

    q.push(s);  // ставить в исходную ячейку

  

    // Сделать BFS, начиная с исходной ячейки

    while (!q.empty())

    {

        queueNode curr = q.front();

        Point pt = curr.pt;

  

        // Если мы достигли целевой ячейки,

        // мы сделали

        if (pt.x == dest.x && pt.y == dest.y)

            return curr.dist;

  

        // Иначе снимаем очередь с передней ячейки в очереди

        // и ставим в очередь соседние ячейки

        q.pop();

  

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

        {

            int row = pt.x + rowNum[i];

            int col = pt.y + colNum[i];

              

            // если соседняя ячейка действительна, имеет путь и

            // еще не посещен, поставьте его в очередь.

            if (isValid(row, col) && mat[row][col] && 

               !visited[row][col])

            {

                // помечаем ячейку как посещенную и ставим ее в очередь

                visited[row][col] = true;

                queueNode Adjcell = { {row, col},

                                      curr.dist + 1 };

                q.push(Adjcell);

            }

        }

    }

  

    // Возвращаем -1, если пункт назначения не может быть достигнут

    return -1;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int mat[ROW][COL] =

    {

        { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },

        { 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },

        { 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },

        { 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 },

        { 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },

        { 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },

        { 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },

        { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },

        { 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 }

    };

  

    Point source = {0, 0};

    Point dest = {3, 4};

  

    int dist = BFS(mat, source, dest);

  

    if (dist != INT_MAX)

        cout << "Shortest Path is " << dist ;

    else

        cout << "Shortest Path doesn't exist";

  

    return 0;

}

Джава

// Java программа для поиска кратчайшего
// путь между указанной исходной ячейкой
// в ячейку назначения.

import java.util.*;

  

class GFG 

{

static int ROW = 9;

static int COL = 10;

  
// Для хранения матричных ячеек

static class Point

{

    int x;

    int y;

  

    public Point(int x, int y)

    {

        this.x = x;

        this.y = y;

    }

};

  
// Структура данных для очереди, используемой в BFS

static class queueNode

{

    Point pt; // Кординаты клетки

    int dist; // расстояние ячейки от источника

  

    public queueNode(Point pt, int dist)

    {

        this.pt = pt;

        this.dist = dist;

    }

};

  
// проверяем, задана ли ячейка (строка, кол)
// является действительной ячейкой или нет.

static boolean isValid(int row, int col)

{

    // возвращаем true если номер строки и

    // номер столбца находится в диапазоне

    return (row >= 0) && (row < ROW) &&

           (col >= 0) && (col < COL);

}

  
// Эти массивы используются для получения строки и столбца
// номера 4 соседей данной ячейки

static int rowNum[] = {-1, 0, 0, 1};

static int colNum[] = {0, -1, 1, 0};

  
// функция, чтобы найти кратчайший путь между
// указанная исходная ячейка для целевой ячейки.

static int BFS(int mat[][], Point src,

                            Point dest)

{

    // проверка исходной и целевой ячейки

    // матрицы имеют значение 1

    if (mat[src.x][src.y] != 1 || 

        mat[dest.x][dest.y] != 1)

        return -1;

  

    boolean [][]visited = new boolean[ROW][COL];

      

    // Пометить исходную ячейку как посещенную

    visited[src.x][src.y] = true;

  

    // Создать очередь для BFS

    Queue<queueNode> q = new LinkedList<>();

      

    // Расстояние исходной ячейки равно 0

    queueNode s = new queueNode(src, 0);

    q.add(s); // ставить в исходную ячейку

  

    // Сделать BFS, начиная с исходной ячейки

    while (!q.isEmpty())

    {

        queueNode curr = q.peek();

        Point pt = curr.pt;

  

        // Если мы достигли целевой ячейки,

        // мы сделали

        if (pt.x == dest.x && pt.y == dest.y)

            return curr.dist;

  

        // Иначе снимаем очередь с передней ячейки

        // в очереди и в очереди

        // его соседние ячейки

        q.remove();

  

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

        {

            int row = pt.x + rowNum[i];

            int col = pt.y + colNum[i];

              

            // если соседняя ячейка действительна, имеет путь

            // и еще не посещенный, поставьте его в очередь.

            if (isValid(row, col) && 

                    mat[row][col] == 1 && 

                    !visited[row][col])

            {

                // помечаем ячейку как посещенную и ставим ее в очередь

                visited[row][col] = true;

                queueNode Adjcell = new queueNode(new Point(row, col),

                                                      curr.dist + 1 );

                q.add(Adjcell);

            }

        }

    }

  

    // Возвращаем -1, если пункт назначения не может быть достигнут

    return -1;

}

  
// Код драйвера

public static void main(String[] args) 

{

    int mat[][] = {{ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },

                   { 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },

                   { 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },

                   { 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 },

                   { 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },

                   { 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },

                   { 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },

                   { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },

                   { 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 }};

  

    Point source = new Point(0, 0);

    Point dest = new Point(3, 4);

  

    int dist = BFS(mat, source, dest);

  

    if (dist != Integer.MAX_VALUE)

        System.out.println("Shortest Path is " + dist);

    else

        System.out.println("Shortest Path doesn't exist");

    }

}

  
// Этот код предоставлен PrinciRaj1992

C #

// C # программа для поиска кратчайшего
// путь между указанной исходной ячейкой
// в ячейку назначения.

using System;

using System.Collections.Generic;

  

class GFG 

{

static int ROW = 9;

static int COL = 10;

  
// Для хранения матричных ячеек

public class Point

{

    public int x;

    public int y;

  

    public Point(int x, int y)

    {

        this.x = x;

        this.y = y;

    }

};

  
// Структура данных для очереди, используемой в BFS

public class queueNode

{

    // Кординаты клетки

    public Point pt; 

      

    // расстояние ячейки от источника

    public int dist; 

  

    public queueNode(Point pt, int dist)

    {

        this.pt = pt;

        this.dist = dist;

    }

};

  
// проверяем, задана ли ячейка (строка, кол)
// является действительной ячейкой или нет.

static bool isValid(int row, int col)

{

    // возвращаем true если номер строки и

    // номер столбца находится в диапазоне

    return (row >= 0) && (row < ROW) &&

           (col >= 0) && (col < COL);

}

  
// Эти массивы используются для получения строки и столбца
// номера 4 соседей данной ячейки

static int []rowNum = {-1, 0, 0, 1};

static int []colNum = {0, -1, 1, 0};

  
// функция, чтобы найти кратчайший путь между
// указанная исходная ячейка для целевой ячейки.

static int BFS(int [,]mat, Point src,

                           Point dest)

{

    // проверка исходной и целевой ячейки

    // матрицы имеют значение 1

    if (mat[src.x, src.y] != 1 || 

        mat[dest.x, dest.y] != 1)

        return -1;

  

    bool [,]visited = new bool[ROW, COL];

      

    // Пометить исходную ячейку как посещенную

    visited[src.x, src.y] = true;

  

    // Создать очередь для BFS

    Queue<queueNode> q = new Queue<queueNode>();

      

    // Расстояние исходной ячейки равно 0

    queueNode s = new queueNode(src, 0);

    q.Enqueue(s); // ставить в исходную ячейку

  

    // Сделать BFS, начиная с исходной ячейки

    while (q.Count != 0)

    {

        queueNode curr = q.Peek();

        Point pt = curr.pt;

  

        // Если мы достигли целевой ячейки,

        // мы сделали

        if (pt.x == dest.x && pt.y == dest.y)

            return curr.dist;

  

        // Иначе снимаем очередь с передней ячейки

        // в очереди и в очереди

        // его соседние ячейки

        q.Dequeue();

  

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

        {

            int row = pt.x + rowNum[i];

            int col = pt.y + colNum[i];

              

            // если соседняя ячейка действительна, имеет путь

            // и еще не посещенный, поставьте его в очередь.

            if (isValid(row, col) && 

                    mat[row, col] == 1 && 

               !visited[row, col])

            {

                // помечаем ячейку как посещенную и ставим ее в очередь

                visited[row, col] = true;

                queueNode Adjcell = new queueNode(new Point(row, col),

                                                      curr.dist + 1 );

                q.Enqueue(Adjcell);

            }

        }

    }

  

    // Возвращаем -1, если пункт назначения не может быть достигнут

    return -1;

}

  
// Код драйвера

public static void Main(String[] args) 

{

    int [,]mat = {{ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },

                  { 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },

                   { 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },

                  { 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 },

                  { 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },

                  { 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },

                  { 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },

                  { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },

                  { 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 }};

  

    Point source = new Point(0, 0);

    Point dest = new Point(3, 4);

  

    int dist = BFS(mat, source, dest);

  

    if (dist != int.MaxValue)

        Console.WriteLine("Shortest Path is " + dist);

    else

        Console.WriteLine("Shortest Path doesn't exist");

    }

}

  
// Этот код предоставлен PrinciRaj1992

Выход :

Shortest Path is 11

Эта статья предоставлена Aditya Goel . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Кратчайший путь в двоичном лабиринте

0.00 (0%) 0 votes