我有一个问题，需要在一个NxM的网格中从点A（始终在左上角）到点B（始终在右下角）找到最短路径，只能向右或向下移动。听起来很简单，对吧？但是这里有个限制：我只能移动当前所在方块上显示的数字。让我来举个例子：
2 5 1 2
9 2 5 3
3 3 1 1
4 8 2 7
在这个4x4的网格中，最短路径需要走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;
}
程序现在可以输出正确的答案。现在我需要优化代码（运行时间太长了）。有什么建议吗？优化是我最不擅长的事情。
答案
最终解决方案似乎只需要很少的代码。越少越好，我喜欢这样。感谢Dejan Jovanović提供了漂亮的解决方案。
#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;
}