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

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

Если вам нужен более простой, но не менее эффективный алгоритм поиска кратчайшего пути, обратите внимание на алгоритм Дейкстры. , который можно рассматривать как более простую версию A*. Это немного медленнее, чем A*, но все же работает очень быстро и гарантирует оптимальный ответ.

Надеюсь это поможет!

Это простая проблема, которую можно решить с помощью поиска в ширину.

 /**
  * computing distance of each cell from the starting cell 
  * avoiding obstacles, 0 represents obstacle 1 represents non obstacle
  * we can take only one step x-1;x+1;y-1;y+1
 */

#include<iostream>
#include<queue>
#include<stdio.h>
using namespace std;

class XY
{
 public :
 int x;
int y;
};

int main()
{
int grid[8][8] = {
    {1,1,1,1,1,1,1,1},
    {1,0,0,0,1,1,1,1},
    {1,1,0,0,1,1,1,1},
    {1,1,0,0,1,1,1,1},
    {1,1,1,2,0,1,0,0},
    {1,1,1,1,1,1,1,1},
    {1,1,1,1,1,1,1,1},
    {1,1,1,1,1,1,1,1}
};


int rows = 8;
int cols = 8;

int distance[rows][cols];

for(int m = 0;m<rows;m++)
{
    for(int n =0;n<cols;n++)
    {
        distance[m][n] = -1;
    }
}

queue<XY> iterator;


XY xy;
xy.x = 0;
xy.y = 0;
distance[0][0] = 0;
iterator.push(xy);

while(!iterator.empty())
{
    xy = iterator.front();
    iterator.pop();
    //printf("popped %d+%d\n",xy.x ,xy.y);
    for(int p = -1;p<2;p++)
    {
        for(int q = -1;q<2;q++)
        {
            if(p == q)continue;
            int i = xy.x + p;
            int j = xy.y + q;

            if(i<0)i=0;
            if(j<0)j=0;
            if(i>rows-1)i=rows-1;
            if(j>cols-1)j=cols-1;

            if(i== xy.x && j == xy.y)continue;

    //              printf("i,j = %d,%d\n",i,j);

            if(distance[i][j] == -1)
            {
     //                 printf("******\n");
                if(grid[i][j] != 0)
                {
     //                 printf("assigned distance %d to %d+%d\n",distance[xy.x][xy.y] + 1,i,i); 
                distance[i][j] = distance[xy.x][xy.y] + 1;
                XY xyn;
                xyn.x = i;
                xyn.y = j;  
                iterator.push(xyn);
      //                    printf("pushed %d+%d\n",xyn.x,xyn.y);
                }
            }

        }
    }
}

for(int x = 0;x<rows;x++)
{
    for(int y =0;y<cols;y++)
    {
        printf("%d ",distance[x][y]);   
    }
    printf("\n");
}
return 0;
}

Я считаю, что данная проблема может быть решена с помощью поиска в ширину (BFS), как упоминалось ранее. Постановка проблемы очень важна. Итак, давайте опишем проблему, а затем перейдем к ее решению.

Описание проблемы:

Вы отвечаете за подготовку недавно купленного участка для нового здания. Участок покрыт траншеями и имеет единственное препятствие, которое необходимо убрать, прежде чем можно будет подготовить фундамент для здания. Робот-разрушитель должен удалить препятствие, прежде чем можно будет двигаться дальше по зданию. Напишите алгоритм для определения минимального расстояния, необходимого роботу-разрушителю для удаления препятствия.

Предположения:

1. Участок плоский, за исключением траншей, и может быть представлен в виде двухмерной сетки.
2. Робот-разрушитель должен начинать с верхнего левого угла участка, который всегда плоский и может перемещаться на один блок вверх, вниз, вправо или влево за раз.
3. Робот-разрушитель не может войти в траншеи и не может покинуть участок.
4. Ровные области представлены как 1, области с траншеями как 0 и препятствия 9.

Вывод:

Возвращает целое число, представляющее минимальное расстояние, пройденное для устранения препятствия, в противном случае возвращает -1.

Решение

from collections import defaultdict

from collections import deque


def is_valid(i, j, m, n, matrix, visited):
    if i >= 0 and j >= 0 \
            and i < m and j < n \
            and visited[i][j] is False \
            and matrix[i][j] in (1, 9):
        return True

    return False


def remove_obstacle(matrix, m, n):
    queue = deque()
    i = 0
    j = 0
    queue.append((i, j, 0))

    visited = [[False for _ in range(n)] for _ in range(m)]
    distance_matrix = [[100 for _ in range(n)] for _ in range(m)]

    visited[i][j] = True

    while queue:
        i, j, distance = queue.popleft()
        distance_matrix[i][j] = distance

        visited[i][j] = True

        if matrix[i][j] == 9:
            return distance
        new_distance = distance + 1
        if is_valid(i + 1, j, m, n, matrix, visited):
            queue.append((i + 1, j, new_distance))

        if is_valid(i - 1, j, m, n, matrix, visited):
            queue.append((i - 1, j, new_distance))

        if is_valid(i, j + 1, m, n, matrix, visited):
            queue.append((i, j + 1, new_distance))

        if is_valid(i, j - 1, m, n, matrix, visited):
            queue.append((i, j - 1, new_distance))

    return -1


if __name__ == '__main__':
    m = 5
    n = 4
    l = [
        [1, 1, 1, 1],
        [0, 1, 1, 1],
        [0, 1, 0, 1],
        [1, 1, 9, 1],
        [0, 0, 1, 1]
    ]

    bfs = remove_obstacle(l, m, n)
    assert bfs == 5

    m = 3
    n = 3
    l = [
        [1, 0, 0],
        [1, 0, 0],
        [1, 9, 1]
    ]

    bfs = remove_obstacle(l, m, n)
    assert bfs == 3