有一个矩阵包含白细胞(表示为1)、黑细胞(表示为0)和只有一个灰色细胞(表示为2),需要在数组[n][n]中从(0,0)变为(n-1,n-1)。
限制条件:
1)路径应该只覆盖白细胞,并且必须经过灰色细胞(该灰色细胞可以在数组中的任何位置)
2)访问过的节点不能再访问。
下面是典型的迷宫问题解决方案,但是这个解决方案不能处理穿越灰色单元格的具体情况…所以你能帮我修改下面的代码来处理具体情况吗?
我的问题是我不知道如何检查灰色细胞?
#include "stdafx.h"
#include "algorithm"
#include <iostream>
#include <fstream>
using namespace std;
#include<stdio.h>
// Maze size
#define N 4
bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N]);
/* A utility function to print solution matrix sol[N][N] */
void printSolution(int sol[N][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
printf(" %d ", sol[i][j]);
printf("\n");
}
}
/* A utility function to check if x,y is valid index for N*N maze */
bool isSafe(int maze[N][N], int x, int y)
{
//solveMazeUtil() to solve the problem. It returns false if no path is possible,
//otherwise return true and prints the path in the form of 1s. Please note that
//there may be more than one solutions, this function prints one of the feasible
if(x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1)
// if (x,y outside maze) return false
return true;
return false;
}
/* This function solves the Maze problem using Backtracking. It mainly uses
solutions.*/
bool solveMaze(int maze[N][N])
{
int sol[N][N] = { {0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
};
if(solveMazeUtil(maze, 0, 0, sol) == false)
{
printf("Solution doesn't exist");
return false;
}
printSolution(sol);
return true;
}
/* A recursive utility function to solve Maze problem */
bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N])
{
// if (x,y is goal) return true
if(x == N-1 && y == N-1)
{
sol[x][y] = 1;
return true;
}
// Check if maze[x][y] is valid
if(isSafe(maze, x, y) == true)
{
// mark x,y as part of solution path
sol[x][y] = 1;
/* Move forward in x direction */
if (solveMazeUtil(maze, x+1, y, sol) == true)
return true;
/* If x moving in x direction doesn't give solution then
Move down in y direction */
if (solveMazeUtil(maze, x, y+1, sol) == true)
return true;
/* If none of the above movements work then BACKTRACK:
unmark x,y as part of solution path */
sol[x][y] = 0;
return false;
}
return false;
}
// driver program to test above function
int main()
{
int maze[N][N] = { {1, 0, 0, 0},
{1, 1, 0, 1},
{0, 1, 0, 0},
{1, 1, 1, 1}
};
solveMaze(maze);
getchar();
return 0;
}
我想的一个解决办法是:
生成所有可能的路径(穿过1或2)。
然后,找出路径中哪个有2然后将该路径打印为输出。
但我不认为这是一个好办法…所以,请让我知道如何以一种体面的方式实现我的目标。
谢谢
最佳答案
因为在您的代码中,您只使用了两种可能的移动:向下和向右,那么这是一个DAGdag适用于动态规划方法:每个单元有两种可能到达那里,一种来自上面,另一种来自左边。因此,单元的最小距离为:
cost[i][j] = min(cost[i][j-1],cost[i-1][j]) + 1
这是考虑到做一个运动的成本是1。如果单元格是黑色的,你可以给它无限的代价,你只需要找到一条从
P1(start)
到P2(gray cell)
的路径,然后找到一条从P2
到P3(goal)
的路径。为了重建路径,您可以创建另一个父
pi[N][N]
矩阵,如果最短路径来自上方,则pi[i][j] = (i-1, j)
如果来自左侧,则pi[i][j] = (i, j-1)
如果无法到达该单元格。关于c++ - 无法在迷宫中追踪灰色细胞,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/19478345/