最短路径中的两点之间的网格。使用catch [英] Shortest path in a grid between two points. With a catch
问题描述
我有这个问题，我必须要找到从A点（始终左上）的N×M个网格的最短路径只向右移动或向下到点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 //高度和宽度
2 5 2 2 //
2 2 7 3 //的
3 1 2 2 //格
4 8 2 7 //
1 1 1 1 //
作业
我想到这通过，但不能得出一个更好的解决方案，而不是简化输入电网到unweighed（或负重量）图，并在其上运行像Dijkstra算法或A *（或类似的规定）。嗯...这是一部分，我迷路了。我实现的东西开始（或东西扔鞭打马上）。它有没有关系Dijkstra算法或A *或任何东西;只是直接的广度优先搜索。
的code
的#include＆LT;的iostream＆GT;
＃包括＆LT;载体＆GT;
结构点;
类型定义的std ::矢量＆lt; INT＆GT; vector_1D;
类型定义的std ::矢量＆lt;的std ::矢量＆lt; INT＆GT; ＆GT; vector_2D;
类型定义的std ::矢量＆lt;点和GT; vector_point;
结构点{
INT Y，X;
vector_point父母;
点（中间体yPos = 0，诠释XPOS = 0）为：y（yPos）中，x（XPOS）{}
void运算符＆LT;＆LT; （常量点和放大器;点）{这 - ＆GT; Parents.push_back（点）; }
};
结构grid_t {
INT高度，宽度;
vector_2D砖;
grid_t（）//构造格
{
给std :: cin＆GT;＆GT;高度＆GT;＆GT;宽度; //输入电网的高度和放大器;宽度
tiles.resize（高度，vector_1D（宽度，0））; //初始化格砖
的for（int i = 0; I＆LT;高度;我++）//
为（诠释J = 0; J＆所述;宽度; J ++）//输入每一瓦片一次一个
给std :: cin＆GT;＆GT;瓷砖[I] [J]。 //通过Grid循环
}
};
无效go_find_it（grid_t＆安培;电网）
{
vector_point openList，closedList;
点previous_node; //点被初始化为（Y = 0，X = 0）如果没有告知，否则
openList.push_back（previous_node）; //（0，0）当然是我们想咨询的第一点，
做
{
closedList.push_back（openList.back（））; //我们是在瓷砖是好的，检查。它标记左右。
openList.pop_back（）; //我们不需要这个家伙没有更多
INT Y = closedList.back（）Y。 //现在，我们将实际
INT X = closedList.back（）×。 //移动到新点
INT跳= grid.tiles [Y] [X] //'跳'是对我们站在瓦片显示的数字。
如果（Y +跳＆LT; grid.height）//如果我们不打算出界
{
openList.push_back（点（Y +跳跃，X））; //
openList.back（）＆其中;＆其中;点（Y，X）; //推入我们在现在的点，因为它的父节点
}
如果（X +跳＆LT; grid.width）//如果我们不打算出界
{
openList.push_back（点（Y，X +跳跃））; //推入新的有希望的点
openList.back（）＆其中;＆其中;点（Y，X）; //推入我们在现在的点，因为它的父节点
}
}
而（openList.size（）大于0）; //当没有新的瓦片，检查，打破了与回报
}
诠释的main（）
{
grid_t网格; //初始化网格
go_find_it（网格）; //基本上蛮力得到它所有算法
返回0;
}
我应该大概还要指出，运行时间不能超过1秒，且最大网格的高度和宽度为1000。所有的瓦片也号码从1至1000。
感谢。
编辑code
的#include＆LT;的iostream＆GT;
＃包括＆LT;载体＆GT;
结构点;
类型定义的std ::矢量＆lt; INT＆GT; vector_1D;
类型定义的std ::矢量＆lt;的std ::矢量＆lt; INT＆GT; ＆GT; vector_2D;
类型定义的std ::矢量＆lt;点和GT; vector_point;
结构点{
INT Y，X，深度;
vector_point父母;
点（中间体yPos = 0，诠释XPOS = 0，诠释dDepth = 0）为：y（yPos）中，x（XPOS），深度（dDepth）{}
void运算符＆LT;＆LT; （常量点和放大器;点）{这 - ＆GT; Parents.push_back（点）; }
};
结构grid_t {
INT高度，宽度;
vector_2D砖;
grid_t（）//构造格
{
给std :: cin＆GT;＆GT;高度＆GT;＆GT;宽度; //输入电网的高度和放大器;宽度
tiles.resize（高度，vector_1D（宽度，0））; //初始化格砖
的for（int i = 0; I＆LT;高度;我++）//
为（诠释J = 0; J＆所述;宽度; J ++）//输入每一瓦片一次一个
给std :: cin＆GT;＆GT;瓷砖[I] [J]。 //通过Grid循环
}
};
INT go_find_it（grid_t＆安培;电网）
{
vector_point openList，closedList;
点previous_node（0，0，0）; //点被初始化为（γ= 0，X = 0，深度= 0），如果没有被告知，否则
openList.push_back（previous_node）; //（0，0）当然是我们想咨询的第一点，
INT min_path = 1000000;
做
{
closedList.push_back（openList [0]）; //我们是在瓷砖是好的，检查。它标记左右。
openList.erase（openList.begin（））; //我们不需要这个家伙没有更多
INT Y = closedList.back（）Y。 //现在我们要实际移动到新点
INT X = closedList.back（）×。 //
。INT深度= closedList.back（）的深度; //新的深度
如果（Y == grid.height-1和;＆放大器，X == grid.width-1）的回报深度; //第一路径是最短的一个。返回它
INT跳= grid.tiles [Y] [X] //'跳'是对我们站在瓦片显示的数字。
如果（Y +跳＆LT; grid.height）//如果我们不打算出界
{
openList.push_back（点（Y +跳跃中，x，深度+ 1））; //
openList.back（）＆其中;＆其中;点（Y，X）; //推入我们在现在的点，因为它的父节点
}
如果（X +跳＆LT; grid.width）//如果我们不打算出界
{
openList.push_back（点（Y，X +跳跃，深度+ 1））; //推入新的有希望的点
openList.back（）＆其中;＆其中;点（Y，X）; //推入我们在现在的点，因为它的父节点
}
}
而（openList.size（）大于0）; //当没有新的瓦片，检查，打破并返回false
返回0;
}
诠释的main（）
{
grid_t网格; //初始化网格
INT min_path = go_find_it（网格）; //基本上蛮力得到它所有算法
性病::法院＆LT;＆LT; min_path＆LT;＆LT;的std :: ENDL;
//系统（暂停）;
返回0;
}
该计划现在打印正确的答案。现在，我必须优化（运行时间是太大了）。就这一个任何提示？优化是一件事，我吮吸。
答案
在最终解决方案出现了由小code。越少越好，因为我喜欢它。由于德扬·约万诺维奇的美丽解决方案
的#include＆LT;的iostream＆GT;
＃包括＆LT;载体＆GT;
＃包括＆LT;算法＆GT;
结构grid_t {
INT高度，宽度;
的std ::矢量＆lt;的std ::矢量＆lt; INT＆GT; ＆GT;瓷砖;
的std ::矢量＆lt;的std ::矢量＆lt; INT＆GT; ＆GT;距离;
grid_t（）//构造格
{
给std :: cin＆GT;＆GT;高度＆GT;＆GT;宽度; //输入电网的高度和放大器;宽度
tiles.resize（身高，标准::矢量＆lt; INT＆GT;（宽度，0））; //初始化格砖
distance.resize（身高，标准::矢量＆lt; INT＆GT;（宽，1000000））; //初始化格砖
的for（int i = 0; I＆LT;高度;我++）//
为（诠释J = 0; J＆所述;宽度; J ++）//输入每一瓦片一次一个
给std :: cin＆GT;＆GT;瓷砖[I] [J]。 //通过Grid循环
}
};
诠释的main（）
{
grid_t网格; //初始化网格
grid.distance [0] [0] = 0;
的for（int i = 0; I＆LT; grid.height;我++）{
对于（INT J = 0; J＆LT; grid.width; J ++）{
如果（grid.distance [I] [J] LT; 1000000）{
INT D = grid.tiles [I] [J]。
如果第（i + D＆所述; grid.height）{
grid.distance [I + D] [J] =标准::分（grid.distance [I] [J] + 1，grid.distance [I + D] [J]）;
}
如果（J + D＆LT; grid.width）{
grid.distance [I] [J + D] =标准::分（grid.distance [I] [J] + 1，grid.distance [I] [J + D]）;
}
}
}
}
如果（grid.distance [grid.height-1] [grid.width-1] == 1000000）grid.distance [grid.height-1] [grid.width-1] = 0;
性病::法院＆LT;＆LT; grid.distance [grid.height-1] [grid.width-1];＆其中;的std :: ENDL;
//系统（暂停）;
返回0;
}
有需要构造图，这可以很容易地解决了使用一个扫描整个矩阵动态规划。
您可以在一开始设定的距离矩阵D [I，J]为+ INF，与D [0,0] = 0，同时穿越你只是做矩阵
如果（D [I，J] 1 + INF）{
INT D = A [I，J]。
如果第（i + D＆其中M）{
D [我+ D，J] = MIN（D [I，J] + 1，D [我+ D，J]）;
}
如果第（j + D＆其中N）{
D [I，J + D] =分钟（D [I，J] + 1，D [I，J + D]）;
}
}
最终的最小距离是在D [M-1，N-1]。如果你想重建的路径，你可以保持一个独立的矩阵标志着那里的最短路径来了。
I have this problem where I have to find the shortest path in an NxM grid from point A (always top left) to point B (always bottom right) by only moving right or down. Sounds easy, eh? Well here's the catch: I can only move the number shown on the tile I'm sitting on at the moment. Let me illustrate:
2 5 1 2
9 2 5 3
3 3 1 1
4 8 2 7
In this 4x4 grid the shortest path would take 3 steps, walking from top left 2 nodes down to 3, and from there 3 nodes right to 1, and then 1 node down to the goal.
[2] 5 1 2
9 2 5 3
[3] 3 1 [1]
4 8 2 [7]
If not for the shortest path, I could also be taking this route:
[2] 5 [1][2]
9 2 5 3
3 3 1 [1]
4 8 2 [7]
That would unfortunately take a whopping 4 steps, and thus, is not in my interest. That should clear things out a bit. Now about the input.
The user inputs the grid as follows:
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 //
Homework
I have thought this through, but cannot come to a better solution than to simplify the inputted grid into an unweighed (or negative-weight) graph and run something like dijkstra or A* (or something along those lines) on it. Well... this is the part where I get lost. I implemented something to begin with (or something to throw to thrash right away). It's got nothing to do with dijkstra or A* or anything; just straight-forward breadth-first search.
The Code
#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;
}
I should probably also point out that the running time cannot exceed 1 second, and the maximum grid height and width is 1000. All of the tiles are also numbers from 1 to 1000.
Thanks.
Edited Code
#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;
}
The program now prints the correct answer. Now I have to optimize (run time is way too big). Any hints on this one? Optimizing is the one thing I suck at.
The Answer
In the end the solution appeared to consist of little code. The less the better, as I like it. Thanks to Dejan Jovanović for the beautiful solution
#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;
}
There is need to construct the graph, this can easily be solved with dynamic programming using one scan over the matrix.
You can set the distance matrix D[i,j] to +inf at the start, with D[0,0] = 0. While traversing the matrix you just do
if (D[i,j] < +inf) {
int d = a[i, j];
if (i + d < M) {
D[i + d, j] = min(D[i,j] + 1, D[i + d, j]);
}
if (j + d < N) {
D[i, j + d] = min(D[i,j] + 1, D[i, j + d]);
}
}
The final minimal distance is in D[M -1, N-1]. If you wish to reconstruct the path you can keep a separate matrix that marks where the shortest path came from.
这篇关于最短路径中的两点之间的网格。使用catch的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
