데이터 구조의 미로 풀이
//SeqStack.h
#pragma once
#include//maze.c
// ：
#include"SeqStack.h"
void SeqStackInit(SeqStack* stack) {
if (stack == NULL) {
return;
}
stack->size = 0;
}
void SeqStackDestory(SeqStack* stack) {
if (stack == NULL) {
return;
}
stack->size = 0;
}
void SeqStackPush(SeqStack* stack, SeqStackType value) {
if (stack == NULL) {
return;
}
if (stack->size >= SeqStackMaxSize)
return;
stack->data[stack->size++] = value;
}
void SeqStackPop(SeqStack* stack) {
if (stack == 0) {
return;
}
if (stack->size == 0)
return;
--stack->size;
}
int GetTop(SeqStack* stack, SeqStackType* value) {
if (stack == NULL || value == NULL) {
return 0;
}
if (stack->size == 0)
return 0;
*value = stack->data[stack->size - 1];
return 1;
}
size_t SeqStackSize(SeqStack* stack) {
if (stack == NULL) {
return 0;
}
return stack->size;
}
void SeqStackAssign(SeqStack* from, SeqStack* to) { //
if (from == NULL || to == NULL) {
return;
}
to->size = from->size;
size_t i = 0;
for (; i < from->size; ++i) {
to->data[i] = from->data[i];
}
}
#ifdef FOR_MAZE
#include
");
return;
}
printf("
[%s]
", msg);
printf("[ ]
");
size_t i = 0;
for (; i < stack->size; ++i) {
printf("(%d, %d)
", stack->data[i].row, stack->data[i].col);
}
printf("[ ]
");
}
#endif
void MazeInit(Maze* maze) {
if (maze == NULL) {
return;
}
int map[MAZE_ROW][MAZE_COL] = {
{0, 1, 0, 0, 0, 0},
{0, 1, 1, 1, 0, 0},
{0, 1, 0, 1, 1, 0},
{0, 1, 1, 0, 0, 0},
{0, 0, 1, 0, 0, 0},
{0, 0, 1, 0, 0, 0}
};
size_t i = 0;
for (; i < MAZE_ROW; ++i) {
size_t j = 0;
for (; j < MAZE_COL; ++j) {
maze->map[i][j] = map[i][j];
}
}
}
void MazeInitMultiExit(Maze* maze) { // ,
if (maze == NULL) {
return;
}
int map[MAZE_ROW][MAZE_COL] = {
{ 0, 1, 0, 0, 0, 0 },
{ 0, 1, 1, 1, 0, 0 },
{ 0, 1, 0, 1, 1, 1 },
{ 1, 1, 1, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0 }
};
size_t i = 0;
for (; i < MAZE_ROW; ++i) {
size_t j = 0;
for (; j < MAZE_COL; ++j) {
maze->map[i][j] = map[i][j];
}
}
}
void MazeInitMultiExitWithCycle(Maze* maze) { //
if (maze == NULL) {
return;
}
int map[MAZE_ROW][MAZE_COL] = {
{ 0, 1, 0, 0, 0, 0 },
{ 0, 1, 1, 1, 0, 0 },
{ 0, 1, 0, 1, 1, 1 },
{ 1, 1, 1, 1, 0, 0 },
{ 0, 0, 1, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0 }
};
size_t i = 0;
for (; i < MAZE_ROW; ++i) {
size_t j = 0;
for (; j < MAZE_COL; ++j) {
maze->map[i][j] = map[i][j];
}
}
}
void MazePrint(Maze* maze) {
if (maze == NULL) {
return;
}
size_t i = 0;
for (; i < MAZE_ROW; ++i) {
size_t j = 0;
for (; j < MAZE_COL; ++j) {
printf("%2d ", maze->map[i][j]);
}
printf("
");
}
printf("
");
}
int CanStay(Maze* maze, Point cur) {
if (maze == NULL) {
return 0;
}
//1.
if (cur.row < 0 || cur.row >= MAZE_ROW||
cur.col < 0 || cur.col >= MAZE_COL) {
return 0;
}
//2. 1.
if (maze->map[cur.row][cur.col] == 1) {
return 1;
}
return 0;
}
void Mark(Maze* maze, Point cur) {
if (maze == NULL) {
return;
}
maze->map[cur.row][cur.col] = 2;
}
int IsExit(Point cur, Point entry) {
//1.
//2.
if (cur.row == 0 || cur.col == 0 ||
cur.row == MAZE_ROW - 1 || cur.col == MAZE_COL - 1) {
//
if (cur.row == entry.row && cur.col == entry.col) {
//
return 0;
}
return 1;
}
return 0;
}
void _HasPath(Maze* maze, Point cur, Point entry) {
if (maze == NULL) {
return;
}
//1. ( 1)
if (!CanStay(maze, cur)) {
return;
}
//2.
Mark(maze, cur);
//3. ( )
if (IsExit(cur, entry)) {
printf(" ！
");
return;
}
//4. ( HasPath)
Point up = cur;
up.row -= 1;
_HasPath(maze, up, entry);
Point right = cur;
right.col += 1;
_HasPath(maze, right, entry);
Point down = cur;
down.row += 1;
_HasPath(maze, down, entry);
Point left = cur;
left.col -= 1;
_HasPath(maze, left, entry);
//5. ，
return;
}
//
void HasPath(Maze* maze, Point entry) {
if (maze == NULL) {
return;
}
_HasPath(maze, entry, entry);
}
void HasPathByLoop(Maze* maze, Point entry) {
if (maze == NULL) {
return;
}
//1. ， ， ，
if (!CanStay(maze, entry)) {
//
return;
}
//2. ，
Mark(maze, entry);
SeqStack stack;
SeqStackInit(&stack);
SeqStackPush(&stack, entry);
//3. ，
Point cur;
while (GetTop(&stack, &cur)) {
//4. ( ， )
if (IsExit(cur, entry)) {
printf(" ！
");
return;
}
//5.
//6. ， ，
// ，
Point up = cur;
up.row -= 1;
if (CanStay(maze, up)) {
Mark(maze, up);
SeqStackPush(&stack, up);
continue;
}
Point right = cur;
right.col += 1;
if (CanStay(maze, right)) {
Mark(maze, right);
SeqStackPush(&stack, right);
continue;
}
Point down = cur;
down.row += 1;
if (CanStay(maze, down)) {
Mark(maze, down);
SeqStackPush(&stack, down);
continue;
}
Point left = cur;
left.col -= 1;
if (CanStay(maze, left)) {
Mark(maze, left);
SeqStackPush(&stack, left);
continue;
}
//7. ，
SeqStackPop(&stack);
}
return;
}
void _GetShortPath(Maze* maze, Point cur, Point entry,
SeqStack* cur_path, SeqStack* short_path) {
//1.
if (!CanStay(maze, cur)) {
return;
}
//2. ， push cur_path
Mark(maze, cur);
SeqStackPush(cur_path, cur);
//3. ，
if (IsExit(cur, entry)) {
//a). cur_path short_path
SeqStackDebugPrintPoint(cur_path, " ！");
if (SeqStackSize(cur_path) < SeqStackSize(short_path)
|| SeqStackSize(short_path) == 0) {
//b). cur_path short_path ，
// short_path
// cur_path short_path。
SeqStackAssign(cur_path, short_path);
printf("
");
}
//c). cur_path ，
SeqStackPop(cur_path);
return;
}
//4.
Point up = cur;
up.row -= 1;
_GetShortPath(maze, up, entry, cur_path, short_path);
Point right = cur;
right.col += 1;
_GetShortPath(maze, right, entry, cur_path, short_path);
Point down = cur;
down.row += 1;
_GetShortPath(maze, down, entry, cur_path, short_path);
Point left = cur;
left.col -= 1;
_GetShortPath(maze, left, entry, cur_path, short_path);
//5. ， cur_path ， return
SeqStackPop(cur_path);
return;
}
void GetShortPath(Maze* maze, Point entry) { //
SeqStack short_path; //
SeqStack cur_path; //
SeqStackInit(&short_path);
SeqStackInit(&cur_path);
_GetShortPath(maze, entry, entry, &cur_path, &short_path);
SeqStackDebugPrintPoint(&short_path, " ");
}
int CanStayWithCycle(Maze* maze, Point cur, Point pre) {
//1. ，
if (cur.row < 0 || cur.row >= MAZE_ROW ||
cur.col < 0 || cur.col >= MAZE_COL) {
return 0;
}
//2. 1
int cur_value = maze->map[cur.row][cur.col];
if (cur_value == 1) {
return 1;
}
//3.
// cur_value - 1 > pre_value
if (pre.row >= 0 && pre.row < MAZE_ROW &&
pre.col >= 0 && pre.col < MAZE_COL) {
int pre_value = maze->map[pre.row][pre.col];
if (cur_value - 1 > pre_value) {
return 1;
}
}
return 0;
}
void MarkWithCycle(Maze* maze, Point cur, Point pre) {
if (pre.row < 0 || pre.row >= MAZE_ROW ||
pre.col < 0 || pre.col >= MAZE_COL) {
//pre
maze->map[cur.row][cur.col] = 2;
return;
}
int pre_value = maze->map[pre.row][pre.col];
maze->map[cur.row][cur.col] = pre_value + 1;
}
void _GetShortPathWithCycle(Maze* maze, Point cur, Point pre, Point entry,
SeqStack* cur_path, SeqStack* short_path) {
//1. ( )
if (!CanStayWithCycle(maze, cur, pre)) {
return;
}
//2. ， ( )，
MarkWithCycle(maze, cur, pre);
SeqStackPush(cur_path, cur);
//3.
if (IsExit(cur, entry)) {
// a). cur_path short_path
SeqStackDebugPrintPoint(cur_path, " ！");
if (SeqStackSize(cur_path) < SeqStackSize(short_path)
|| SeqStackSize(short_path) == 0) {
// b). cur_path ， short_path
SeqStackAssign(cur_path, short_path);
}
// c). ，
SeqStackPop(cur_path);
return;
}
//4. ， ， ，
Point up = cur;
up.row -= 1;
_GetShortPathWithCycle(maze, up, cur, entry, cur_path, short_path);
Point right = cur;
right.col += 1;
_GetShortPathWithCycle(maze, right, cur, entry, cur_path, short_path);
Point down = cur;
down.row += 1;
_GetShortPathWithCycle(maze, down, cur, entry, cur_path, short_path);
Point left = cur;
left.col -= 1;
_GetShortPathWithCycle(maze, left, cur, entry, cur_path, short_path);
//5. ， ，
SeqStackPop(cur_path);
return;
}
void GetShortPathWithCycle(Maze* maze, Point entry) {
SeqStack short_path; //
SeqStack cur_path; //
SeqStackInit(&short_path);
SeqStackInit(&cur_path);
Point pre = { -1, -1 };
_GetShortPathWithCycle(maze, entry, pre, entry, &cur_path, &short_path);
SeqStackDebugPrintPoint(&short_path, " ");
}
//////////////////////////////////////////
////////// //////////////////
//////////////////////////////////////////
#define TEST_HEADER printf("
======%s======
", __FUNCTION__)
void Test1() {
TEST_HEADER;
Maze maze;
MazeInit(&maze);
MazePrint(&maze);
}
void Test2() {
TEST_HEADER;
Maze maze;
MazeInit(&maze);
Point entry = { 0, 1 };
HasPath(&maze, entry);
MazePrint(&maze);
}
void Test3() {
TEST_HEADER;
Maze maze;
MazeInit(&maze);
Point entry = { 0, 1 };
HasPathByLoop(&maze, entry); //
MazePrint(&maze);
}
void Test4() {
TEST_HEADER;
Maze maze;
MazeInitMultiExit(&maze);
Point entry = { 0, 1 };
GetShortPath(&maze, entry);
MazePrint(&maze);
}
void Test5() {
TEST_HEADER;
Maze maze;
MazeInitMultiExitWithCycle(&maze);
Point entry = { 0, 1 };
GetShortPathWithCycle(&maze, entry);
MazePrint(&maze);
}
int main() {
Test1();
Test2();
Test3();
Test4();
Test5();
system("pause");
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
C 언어 체인 시계는 뱀을 탐식하는 작은 게임을 실현한다본고의 실례는 여러분에게 C 언어 체인표가 뱀 탐식 게임을 실현하는 구체적인 코드를 공유하여 참고하도록 하였으며, 구체적인 내용은 다음과 같다. 프로젝트 이름: 뱀놀이 운영 환경: Linux 프로그래밍 언어: C 언...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
