Кратчайший путь в сетке между двумя точками. С уловом

У меня есть проблема, когда я должен найти кратчайший путь в сетке NxM от точки A (всегда вверху слева) до точки B (всегда внизу справа), двигаясь только вправо или вниз. Звучит легко, а? Ну, вот подвох: я могу перемещать только число, указанное на плитке, на которой я сижу в данный момент. Позвольте мне проиллюстрировать:

2 5 1 2
9 2 5 3
3 3 1 1
4 8 2 7

В этой сетке 4×4 самый короткий путь будет состоять из 3 шагов, проходя сверху слева от 2 узлов до 3, а оттуда 3 узла прямо до 1, а затем 1 узел до цели.

[2] 5  1  2
9  2  5  3
[3] 3  1 [1]
4  8  2 [7]

Если бы не самый короткий путь, я мог бы также взять этот маршрут:

[2] 5 [1][2]
9  2  5  3
3  3  1 [1]
4  8  2 [7]

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

Пользователь вводит сетку следующим образом:

5 4      // height and width
2 5 2 2  //
2 2 7 3  // the
3 1 2 2  // grid
4 8 2 7  //
1 1 1 1  //

Домашнее задание

Я продумал это до конца, но не могу прийти к лучшему решению, чем упростить введенную сетку в невзвешенный (или с отрицательным весом) граф и запустить на нем что-то вроде dijkstra или A * (или что-то подобное). Ну … это та часть, где я заблудился. Я реализовал что-то для начала (или что-то, чтобы бросить прямо сейчас). Это не имеет ничего общего с dijkstra или A * или чем-либо еще; просто прямой поиск в ширину.

Код

#include <iostream>
#include <vector>

struct Point;

typedef std::vector<int> vector_1D;
typedef std::vector< std::vector<int> > vector_2D;
typedef std::vector<Point> vector_point;

struct Point {
int y, x;
vector_point Parents;
Point(int yPos = 0, int xPos = 0) : y(yPos), x(xPos) { }

void operator << (const Point& point) { this->Parents.push_back(point); }
};

struct grid_t {
int height, width;
vector_2D tiles;

grid_t() // construct the grid
{
std::cin >> height >> width; // input grid height & width

tiles.resize(height, vector_1D(width, 0)); // initialize grid tiles

for(int i = 0; i < height; i++)     //
for(int j = 0; j < width; j++)  // input each tile one at a time
std::cin >> tiles[i][j];    // by looping through the grid
}
};

void go_find_it(grid_t &grid)
{
vector_point openList, closedList;
Point previous_node; // the point is initialized as (y = 0, x = 0) if not told otherwise
openList.push_back(previous_node); // (0, 0) is the first point we want to consult, of course

do
{
closedList.push_back(openList.back()); // the tile we are at is good and checked. mark it so.
openList.pop_back(); // we don't need this guy no more

int y = closedList.back().y; // now we'll actually
int x = closedList.back().x; // move to the new point

int jump = grid.tiles[y][x]; // 'jump' is the number shown on the tile we're standing on.

if(y + jump < grid.height) // if we're not going out of bounds
{
openList.push_back(Point(y+jump, x)); //
openList.back() << Point(y, x); // push in the point we're at right now, since it's the parent node
}
if(x + jump < grid.width) // if we're not going out of bounds
{
openList.push_back(Point(y, x+jump)); // push in the new promising point
openList.back() << Point(y, x); // push in the point we're at right now, since it's the parent node
}
}
while(openList.size() > 0); // when there are no new tiles to check, break out and return
}

int main()
{
grid_t grid; // initialize grid

go_find_it(grid); // basically a brute-force get-it-all-algorithm

return 0;
}

Я, вероятно, также должен отметить, что время выполнения не может превышать 1 секунду, а максимальная высота и ширина сетки равна 1000. Все плитки также являются числами от 1 до 1000.

Благодарю.

Отредактированный код

#include <iostream>
#include <vector>

struct Point;

typedef std::vector<int> vector_1D;
typedef std::vector< std::vector<int> > vector_2D;
typedef std::vector<Point> vector_point;

struct Point {
int y, x, depth;
vector_point Parents;
Point(int yPos = 0, int xPos = 0, int dDepth = 0) : y(yPos), x(xPos), depth(dDepth) { }

void operator << (const Point& point) { this->Parents.push_back(point); }
};

struct grid_t {
int height, width;
vector_2D tiles;

grid_t() // construct the grid
{
std::cin >> height >> width; // input grid height & width

tiles.resize(height, vector_1D(width, 0)); // initialize grid tiles

for(int i = 0; i < height; i++)     //
for(int j = 0; j < width; j++)  // input each tile one at a time
std::cin >> tiles[i][j];    // by looping through the grid
}
};

int go_find_it(grid_t &grid)
{
vector_point openList, closedList;
Point previous_node(0, 0, 0); // the point is initialized as (y = 0, x = 0, depth = 0) if not told otherwise
openList.push_back(previous_node); // (0, 0) is the first point we want to consult, of course

int min_path = 1000000;

do
{
closedList.push_back(openList[0]); // the tile we are at is good and checked. mark it so.
openList.erase(openList.begin()); // we don't need this guy no more

int y = closedList.back().y; // now we'll actually move to the new point
int x = closedList.back().x; //
int depth = closedList.back().depth; // the new depth

if(y == grid.height-1 && x == grid.width-1) return depth; // the first path is the shortest one. return it

int jump = grid.tiles[y][x]; // 'jump' is the number shown on the tile we're standing on.

if(y + jump < grid.height) // if we're not going out of bounds
{
openList.push_back(Point(y+jump, x, depth+1)); //
openList.back() << Point(y, x); // push in the point we're at right now, since it's the parent node
}
if(x + jump < grid.width) // if we're not going out of bounds
{
openList.push_back(Point(y, x+jump, depth+1)); // push in the new promising point
openList.back() << Point(y, x); // push in the point we're at right now, since it's the parent node
}
}
while(openList.size() > 0); // when there are no new tiles to check, break out and return false

return 0;
}

int main()
{
grid_t grid; // initialize grid

int min_path = go_find_it(grid); // basically a brute-force get-it-all-algorithm

std::cout << min_path << std::endl;
//system("pause");
return 0;
}

Программа теперь печатает правильный ответ. Теперь я должен оптимизировать (время выполнения слишком велико). Есть намеки на это? Оптимизация — это то, что мне не нравится.

Ответ

В конце концов решение оказалось состоять из небольшого кода. Чем меньше, тем лучше, как мне это нравится. Спасибо Деян Йованович за прекрасное решение

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

struct grid_t {
int height, width;
std::vector< std::vector<int> > tiles;
std::vector< std::vector<int> > distance;

grid_t() // construct the grid
{
std::cin >> height >> width; // input grid height & width

tiles.resize(height, std::vector<int>(width, 0)); // initialize grid tiles
distance.resize(height, std::vector<int>(width, 1000000)); // initialize grid tiles

for(int i = 0; i < height; i++)     //
for(int j = 0; j < width; j++)  // input each tile one at a time
std::cin >> tiles[i][j];    // by looping through the grid
}
};

int main()
{
grid_t grid; // initialize grid

grid.distance[0][0] = 0;
for(int i = 0; i < grid.height; i++) {
for(int j = 0; j < grid.width; j++) {
if(grid.distance[i][j] < 1000000) {
int d = grid.tiles[i][j];
if (i + d < grid.height) {
grid.distance[i+d][j] = std::min(grid.distance[i][j] + 1, grid.distance[i+d][j]);
}
if (j + d < grid.width) {
grid.distance[i][j+d] = std::min(grid.distance[i][j] + 1, grid.distance[i][j+d]);
}
}
}
}
if(grid.distance[grid.height-1][grid.width-1] == 1000000) grid.distance[grid.height-1][grid.width-1] = 0;
std::cout << grid.distance[grid.height-1][grid.width-1] << std::endl;
//system("pause");
return 0;
}