我有一个用随机数[ 0, 1, 2 ]填充的20x30矩阵。我需要找到一条只有1的路径，从左上角开始，到右下角结束。我需要帮助找到1的路径。此外，我如何打印我踩过的每个数字的坐标？我可以显示我踩过的数字，但我在显示它的坐标时遇到了问题。这是我当前的代码
#include <iostream>
#include <vector>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int N = 3;
const int M = 3;
void mtxFeltolt(int (&mat)[N][M]);
void mtxPrint(int (&mat)[N][M]);
void printPaths(int mat[M][N], vector<int> &route, int i, int j)
{
// if last cell is reached
if (i == M - 1 && j == N - 1)
{
// print the current route
for (int i: route) {
cout << i << " - ";
}
cout << mat[i][j] << endl;
return;
}
// include current cell in route
route.push_back(mat[i][j]);
// move right
if (j + 1 < N){
printPaths(mat, route, i, j + 1);
}
// move down
if (i + 1 < M){
printPaths(mat, route, i + 1, j);
}
// move diagonally
if (i + 1 < M && j + 1 < N){
printPaths(mat, route, i + 1, j + 1);
}
// backtrack
route.pop_back();
}
// Print all shortest routes in a rectangular grid
void printPaths(int mat[][N])
{
// vector to store current route
vector<int> route;
// start from the first cell (0, 0)
printPaths(mat, route, 0, 0);
}
// main function
int main()
{
int mat[N][M];
srand (time(NULL));
mtxFeltolt(mat);
cout << "A matrix: " <<endl;
mtxPrint(mat);
cout << endl;
cout << "---- A megfelelo utak ----" << endl;
printPaths(mat);
return 0;
}
void mtxFeltolt(int (&mat)[N][M]){
for(int i=0; i < N; i++){
for(int j=0; j < M; j++)
mat[i][j] = rand() % 3;
}
}
void mtxPrint(int (&mat)[N][M]){
for(int i=0; i < N; i++){
for(int j = 0; j < M; j++){
cout << mat[i][j] << " ";
}
cout << endl;
}
}
希望您能理解这段代码。我没有使用std::pair，而是制作了一个简单的结构Coord来包含路径中坐标的行和列。这样读起来更容易。我还提供了一种生成随机数的更好方法。
我使用深度优先搜索来找到路径。它不能保证最短的路径，但它会从左上角到右下角找到一条路径。
#include <algorithm>
#include <iostream>
#include <random>
#include <vector>
struct Coord {unsigned long row, col;};
template<typename T>
using Matrix = std::vector<std::vector<T>>;
using Path = std::vector<Coord>;
/**
* Generate a random number from [low, high]
*
* @param low The lower bound
* @param high The upper bound
* @return A random number on the range [low, high]
*/
int random_int(int low, int high)
{
static std::random_device rd;
// static std::mt19937 mt(rd()); // different random numbers each time
static std::mt19937 mt(30); // seed that generates a matrix with a path
std::uniform_int_distribution<> dist(low, high);
return dist(mt);
}
Matrix<int> generateMatrix(const int m, const int n)
{
Matrix<int> mat;
for(int row = 0; row < m; ++row)
{
mat.push_back({});
for(int col = 0; col < n; ++col)
{
mat[row].push_back(random_int(0,2));
}
}
return mat;
}
void print(const Matrix<int>& mat)
{
for(const auto & row : mat)
{
for(const auto & col : row)
std::cout << col << " ";
std::cout << std::endl;
}
}
Path findPath(const Matrix<int>& mat,
Matrix<bool>& visited,
const Coord cur,
const Coord end)
{
// out of range -> no path
if(cur.row < 0
|| cur.row >= mat.size()
|| cur.col < 0
|| cur.col >= mat[0].size())
{
return {};
}
// visited current location -> no path
if(visited[cur.row][cur.col])
{
return {};
}
visited[cur.row][cur.col] = true;
// current location is not a 1 -> no path
if(mat[cur.row][cur.col] != 1)
{
return {};
}
// if at the end, the path is trivial
if(cur.row == end.row && cur.col == end.col)
{
return {cur};
}
Path p {cur};
std::vector<Path> paths;
// try to go in each direction
// right
paths.push_back(findPath(mat, visited, {cur.row, cur.col+1}, end));
// left
paths.push_back(findPath(mat, visited, {cur.row, cur.col-1}, end));
// up
paths.push_back(findPath(mat, visited, {cur.row-1, cur.col}, end));
// down
paths.push_back(findPath(mat, visited, {cur.row+1, cur.col}, end));
// up-right
paths.push_back(findPath(mat, visited, {cur.row-1, cur.col+1}, end));
// down-right
paths.push_back(findPath(mat, visited, {cur.row+1, cur.col+1}, end));
// down-left
paths.push_back(findPath(mat, visited, {cur.row+1, cur.col-1}, end));
// up-left
paths.push_back(findPath(mat, visited, {cur.row-1, cur.col-1}, end));
Path longest = *std::max_element(paths.begin(), paths.end(),
[](const auto a, const auto b){
return a.size() < b.size();
});
p.insert(p.end(), longest.begin(), longest.end());
return p;
}
Path findPath(const Matrix<int>& mat,
const Coord cur,
const Coord end)
{
Matrix<bool> visited;
for(int row = 0; row < mat.size(); ++row)
{
visited.push_back({});
for(int col = 0; col < mat[0].size(); ++col)
{
visited[row].push_back(false);
}
}
return findPath(mat, visited, cur, end);
}
int main()
{
auto mat = generateMatrix(5, 5);
print(mat);
auto path = findPath(mat, {0, 0}, {mat.size()-1, mat[0].size()-1});
if(path.size() > 0
&& path.back().row == mat.size()-1 && path.back().col == mat[0].size()-1)
{
std::cout << "path length: " << path.size() << std::endl;
for(const auto c : path)
{
std::cout << "(" << c.row << ", " << c.col << ")" << std::endl;
}
}
else
std::cout << "no path" << std::endl;
}