gpt4 book ai didi

c++ - 初学者在 2D 网格上与 Lee 算法作斗争

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:15:19 25 4
gpt4 key购买 nike

我正在尝试在 2D 网格上实现 Lee 算法。然而,洪水循环停止得太早,声称没有找到更多的“空”单元格。我完全不知道为什么。

#define WIDTH 6
#define HEIGHT 6
int gridArray[WIDTH][HEIGHT];

void InitialiseGrid() {
srand(time(NULL)); // initialise the randomiser

for (int y = 0; y < HEIGHT; y++) {
for (int x = 0; x < WIDTH; x++) {

if (rand() % 4 == 0)
gridArray[x][y] = -2;
else
gridArray[x][y] = -1;
}
}
}

bool foundEmpty = true;
bool foundEnd = false;

int it = 0;

while (foundEmpty && !foundEnd) {
DrawGrid();
cout << endl << endl;
for (int y = 0; y < HEIGHT; y++) {
for (int x = 0; x < WIDTH; x++) {
if (gridArray[x][y] == it) {
// initially assume neighbouring cells are not empty
foundEmpty = false;

// check east cell
if (x < WIDTH) {
int *e = &gridArray[x + 1][y];
if (*e == -1) {
*e = it + 1;
foundEmpty = true;
}
else if (*e == -3) {
foundEnd = true;
}
}

// check west cell
if (x > 0) {
int *w = &gridArray[x - 1][y];
if (*w == -1) {
*w = it + 1;
foundEmpty = true;
}
else if (*w == -3) {
foundEnd = true;
}
}

// check south cell
if (y < HEIGHT) {
int *s = &gridArray[x][y + 1];
if (*s == -1) {
*s = it + 1;
foundEmpty = true;
}
else if (*s == -3) {
foundEnd = true;
}
}

// check north cell
if (y > 0) {
int *n = &gridArray[x][y - 1];
if (*n == -1) {
*n = it + 1;
foundEmpty = true;
}
else if (*n == -3) {
foundEnd = true;
}
}
}
}
}
it++;
}


void DrawGrid() {
std::string message = "";

for (int y = 0; y < HEIGHT; y++) {
cout << endl;
for (int x = 0; x < WIDTH; x++) {
if (gridArray[x][y] == 0)
message = "start";
else if (gridArray[x][y] == -3)
message = "end";
else if (gridArray[x][y] == -2)
message = "X";
else
message = std::to_string(gridArray[x][y]);

cout << "|" << "\t" << message << "\t" << "|";
}
cout << endl;
}
}

路径的终点是通过将单元分配给 -3 来指定的。阻塞的单元格为 -2。空单元格为 -1。起始单元格为0。

最佳答案

不确定您的问题是什么,但您的算法似乎很可靠。我稍微清理了一下,它似乎工作正常:

#include <iostream>
#include <string>
#include <iomanip>

#define WIDTH 7
#define HEIGHT 7

int gridArray[WIDTH][HEIGHT] =
{
{ -1,-1,-1,0,-2,-1,-2 },
{ -2,-1,-1,-1,-1,-2,-2 },
{ -2,-1,-1,-1,-1,-2,-2 },
{ -2,-2,-1,-1,-1,-2,-1 },
{ -1,-2,-2,-2,-1,-1,-2 },
{ -1,-2,-1,-1,-1,-2,-2 },
{ -2,-2,-3,-1,-1,-2,-2 }
};

void DrawGrid()
{
for (int x = 0; x < WIDTH; x++)
{
for (int y = 0; y < HEIGHT; y++)
{
std::string message;

if (gridArray[x][y] == 0)
message = "S";
else if (gridArray[x][y] == -3)
message = "E";
else if (gridArray[x][y] == -2)
message = "#";
else if (gridArray[x][y] == -1)
message = ".";
else
message = std::to_string(gridArray[x][y]);

std::cout << std::setw(3) << message << " ";
}
std::cout << std::endl << std::endl;
}
std::cout << std::endl << std::endl;
}

void SolveMaze()
{
bool foundEnd = false;
int it = 0;

while (!foundEnd)
{
bool foundEmpty = false;
for (int x = 0; x < WIDTH && !foundEnd; ++x)
{
for (int y = 0; y < HEIGHT; ++y)
{
if (gridArray[x][y] == it)
{
// check east cell
if (x < WIDTH - 1)
{
int &east = gridArray[x + 1][y];
if (east == -3)
{
foundEnd = true;
break;
}
else if (east == -1)
{
east = it + 1;
foundEmpty = true;
}
}

// check west cell
if (x > 0)
{
int &west = gridArray[x - 1][y];
if (west == -3)
{
foundEnd = true;
break;
}
else if (west == -1)
{
west = it + 1;
foundEmpty = true;
}
}

// check south cell
if (y < HEIGHT - 1)
{
int &south = gridArray[x][y + 1];
if (south == -3)
{
foundEnd = true;
break;
}
else if (south == -1)
{
south = it + 1;
foundEmpty = true;
}
}

// check north cell
if (y > 0)
{
int &north = gridArray[x][y - 1];
if (north == -3)
{
foundEnd = true;
break;
}
else if (north == -1)
{
north = it + 1;
foundEmpty = true;
}
}
}
}
}

if (!foundEnd && !foundEmpty)
{
std::cout << "This maze has no solution!" << std::endl << std::endl;
break;
}

it++;
}
}

int main()
{
DrawGrid();
SolveMaze();
DrawGrid();
system("pause");
return 0;
}

enter image description here

关于c++ - 初学者在 2D 网格上与 Lee 算法作斗争,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47732364/

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