Планирование пути с использованием 2D-массива

Question

Проблема требует ввода пользователем размера 2D сетки. Затем введите каждую из записей.

Как это:

5 5

-1 -1 -1 -1 -1
-1 0 0 0 -1
-1 1 -1 0 -1
-1 0 0 -2 -1
-1 -1 -1 -1 -1

Тогда на выходе должно быть 3. Какой самый маленький путь от начальной точки "1" до конечной точки "-2". Где «-1» - препятствие, 0 - допустимое пространство.

Метод, данный инструктором:

сначала найдите начальную точку "1". Заполнение его допустимого пространства 4-соседями (слева, справа, вверх и вниз) с помощью "2"

Затем повторите шаги, заполнив допустимое пространство для соседей на «3» и т. Д.

Когда возможное допустимое пространство равно «-2». Остановитесь и распечатайте минимальное количество шагов.

Я постараюсь выписать это.

1. Найдите начальную точку.

   -1 -1 -1 -1 -1
   -1 0 0 0 -1
   -1 **1** -1 0 -1
   -1 0 0 -2 -1
   -1 -1 -1 -1 -1
   

2. Замените соседей "0" на "2" и найдите другое возможное допустимое пространство.

   -1 -1 -1 -1 -1
   -1 **2** **0** 0 -1
   -1 1 -1 0 -1
   -1 **2** **0** -2 -1
   -1 -1 -1 -1 -1
   

3. Повторите шаги.

   -1 -1 -1 -1 -1
   -1 2 3 **0** -1
   -1 1 -1 0 -1
   -1 2 3 **-2** -1
   -1 -1 -1 -1 -1
   

Как сосед "-2". Итак, кратчайший путь - 3.

// Find the Starting point " 1 ". 

#include <iostream>

using namespace std;

const int MAX_SIZE = 100;


///////// DO NOT MODIFY ANYTHING ABOVE THIS LINE /////////

// IMPORTANT:  Do NOT change any of the function headers already provided to you
//             It means that you will need to use the function headers as is


// You may implement additional functions here

bool NextFill(int(&map)[MAX_SIZE][MAX_SIZE], int n)
{
 const int offx = { -1, 0, 0, 1 };
 const int offy = { 0, -1, 1, 0 }
 bool found = false;
 for (int x = 0; x != MAX_SIZE; ++x) {
     for (int y = 0; y != MAX_SIZE; ++y) {
         if (map[x][y] == n) {
             for (int i = 0; i != 4) {
                 auto& neighbor = map[x + offx[i]][y + offy[i]];

                 if (neighbor == -1) {  } 
                 else if (neighbor == -2) { found = true; } 
                 else if (neighbor == 0) { neighbor = n + 1; } 

             }
         }
     }
 }
 return found;
}

// Function: find the smallest number of steps to go from the starting point
//           to the destination in a given map.
//
// Input: int map[][]: 2D-array map
//        int map_h: the height of the map
//        int map_w: the width of the map
// Output: return true if a path is found, and store the smallest number of
//                      steps taken in &num_steps (pass-by-reference)
//         return false if there is no path
// ==============================================================
bool FindPath(int map[][MAX_SIZE], int map_h, int map_w, int& num_steps)
{
 // ==========================
 int time = 0;
 if (NextFill(map, time))
     return true;
 else
     return false;
}

///////// DO NOT MODIFY ANYTHING BELOW THIS LINE /////////

// Function: main function
// ==============================================================
int main()
{
 int map_h;
 int map_w;
 cin >> map_h >> map_w;

 int map[MAX_SIZE][MAX_SIZE];

 // initialize map
 for (int i = 0; i < MAX_SIZE; i++)
     for (int j = 0; j < MAX_SIZE; j++)
         map[i][j] = -1;

 // read map from standard input
 for (int i = 0; i < map_h; i++)
     for (int j = 0; j < map_w; j++)
         cin >> map[i][j];

 int steps;
 // print to screen number of steps if a path is found, otherwise print "No"
 if (FindPath(map, map_h, map_w, steps))
     cout << steps << endl;

 else
     cout << "No" << endl;

}

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

Однако я не могу включить заголовок в мою программу.

Спасибо за чтение длинного длинного вопроса:)!

Answer 1

Вы должны либо хранить в какой-то очереди ваши открытые узлы, либо каждый раз заполнять всю карту:

bool NextFill(int (&map)[MAX_SIZE][MAX_SIZE], int n)
{
    const int offx = {-1, 0, 0, 1};
    const int offy = {0, -1, 1, 0}
    bool found = false;
    for (int x = 0; x != MAX_SIZE; ++x) {
        for (int y = 0; y != MAX_SIZE; ++y) {
            if (map[x][y] == n) {
                 for (int i = 0; i != 4) {
                     auto& neighbor = map[x + offx[i]][y + offy[i]];

                     if (neighbor == -1) { /*Nothing*/ } // wall
                     else if (neighbor == -2) { found = true; } // Found
                     else if (neighbor == 0) { neighbor = n + 1; } // unvisited
                     // else {/*Nothing*/} // Already visited.
                 }
            }
        }
    }
    return found;
}