gpt4 book ai didi

c++ - 在矩阵中查找从左上角到右下角的路径时遇到问题吗?

转载 作者:行者123 更新时间:2023-12-02 07:41:42 24 4
gpt4 key购买 nike

我有一个 20x30 矩阵,其中填充了随机数 [ 0, 1, 2 ]。我需要找到一条仅由 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;
}

关于c++ - 在矩阵中查找从左上角到右下角的路径时遇到问题吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/60643159/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com