역 추적 과 재 귀 두 가지 알고리즘 을 사용 하여 간단 한 미로 (단일 통로 미로) 를 실현 합 니 다.
14504 단어 데이터 구조
간단 한 미궁의 예 를 들 면, 000, 000, 000, 000, 000, 000, 01, 1000, 01, 0, 01, 01, 01, 01, 01, 01, 01, 01, 01, 01, 01, 0 은 통 하지 않 는 다 는 뜻 이 고, 1 은 통 하지 않 는 다 는 뜻 이다.다음은 역 추적 법 과 재 귀 법 으로 이 미 로 를 실현 한다.1. [역 추적 법]
#include
");
return;
}
else
{
s->array[s->top] = data;
s->top++;
return;
}
}
void StackPop(Stack* s)//
{
if (s->top == 0)
{
printf(" ！
");
}
else
{
s->top--;
}
}
DataType StackTop(Stack* s)//
{
assert(!StackEmpty(s));
return s->array[(s->top)-1];
}
void Print(Stack* s)//
{
int i = 0;
for (i =```````
(s->top) - 1; i >= 0; i--)
{
printf("%d
", s->array[i]);
}
printf("
");
}#pragma once
#include
");
}
}
int IsValidEnter(Maze* m, Position enter)//
{
if (NULL == m)
{
return 0;
}
else
{
return 1 == m->_map[enter._x][enter._y];// 1
}
}
int IsExit(Maze* m, Position cur, Position enter)//
{
if (cur._x == enter._x&&cur._y == enter._y)// ，
{
return 0;
}
if (0 == cur._x || MAX_ROW - 1 == cur._x || 0 == cur._y || MAX_COL - 1 == cur._y)//
{
return 1;
}
return 0;
}
int IsPass(Maze*m, Position next)//
{
if (NULL == m)
{
return 0;
}
return 1 == m->_map[next._x][next._y];// 1
}
void PassMaze(Maze* m, Position enter, Stack* s)//
{
Position next;
// ， ，
if (!IsValidEnter(m, enter))
{
printf("
");
return;
}
else
{
StackPush(s, enter);
}
while (!StackEmpty(s))
{
Position cur = StackTop(s);// ，
m->_map[cur._x][cur._y] = 2;// 2，
if (IsExit(m, cur,enter))// ， 、 、 、 ， ，
{
return;
}
else
{
//
next = cur;
next._x -= 1;
if (IsPass(m, next))
{
StackPush(s, next);
continue;
}
//
next = cur;
next._y -= 1;
if (IsPass(m, next))
{
StackPush(s, next);
continue;
}
//
next = cur;
next._y += 1;
if (IsPass(m, next))
{
StackPush(s, next);
continue;
}
//
next = cur;
next._x += 1;
if (IsPass(m, next))
{
StackPush(s, next);
continue;
}
// ， 3， （ ）
m->_map[cur._x][cur._y] = 3;
StackPop(s);
continue;
}
}
}void TestMap()
{
Maze m;
Position enter;
Stack s;
int map[MAX_ROW][MAX_COL] = {
{ 0, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0 },
{ 0, 0, 1, 1, 1, 0 },
{ 0, 0, 1, 0, 1, 1 },
{ 0, 0, 1, 0, 0, 0 } };
InitMap(&m, map);
PrintMap(&m);
printf("
");
StackInit(&s);
enter._x = 5;
enter._y = 2;
PassMaze(&m, enter,&s);
PrintMap(&m);
}2. 【 재 귀 】 재 귀 법 은 스 택 을 사용 할 필요 가 없 기 때문에 스 택 의 헤더 파일 을 더 이상 인용 할 필요 가 없습니다. 미로 함수 가 바 뀌 어야 하 는 것 을 제외 하고 나머지 부분 은 바 꿀 필요 가 없습니다.
int PassMaze(Maze* m, Position enter,Position cur)
{
Position next;
/*if (!IsValidEnter(m, enter))
{
printf("
");
}*/
if (1 == m->_map[cur._x][cur._y])
{
m->_map[cur._x][cur._y] = 2;
if (IsExit(m, cur, enter))
{
return 1;
}
//
next = cur;
next._x -= 1;
if (PassMaze(m, enter, next))
return 1;
//
next = cur;
next._y -= 1;
if (PassMaze(m, enter, next))
return 1;
//
next = cur;
next._y += 1;
if (PassMaze(m, enter, next))
return 1;
//
next = cur;
next._x += 1;
if (PassMaze(m, enter, next))
return 1;
//
m->_map[cur._x][cur._y] = 3;
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
