C 언어 는 간단 한 미로 - 역 추적 법 (재 귀) 을 실현 한다.

우선 역 추적 법 을 알 아 보 겠 습 니 다.역 추적 법: 하나의 노드 는 여러 개의 노드 를 포함 하고 모든 노드 는 몇 개의 검색 분기 의 문제 에서 원래 의 문 제 를 몇 개의 키 문제 로 분해 하여 해결 하 는 알고리즘 이다.한 노드 를 검색 하여 더 이상 검색 할 수 없 음 을 발견 하면 검색 과정 을 이 노드 의 이전 노드 로 거 슬러 올 라 가 이 노드 밖의 다른 검색 되 지 않 은 가 지 를 계속 검색 합 니 다.이 노드 가 더 이상 검색 할 수 없 음 을 발견 하면 검색 과정 을 이 노드 의 앞 지점 으로 거 슬러 올 라 가 이러한 검색 과정 을 계속 합 니 다.이러한 검색 과정 은 문제 의 해 제 를 검색 하거나 모든 검색 가능 한 지점 이 존재 하지 않 을 때 까지 진행 된다.
미로:
0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 1 1 1 1 0 1 0 0 0 0
사고방식: 1. 미궁 지도의 입구 좌 표를 전송 하여 입구 좌표 가 정확 한 지 판단 한다.2. 미 로 를 시작 하여 현재 좌표 (Cur) 를 창고 에 넣 고 어느 방향 으로 가 려 고 합 니 다.
위: 위로 올 라 가면 위 에서 걸 을 수 있 는 지 여 부 를 판단 하고 위로 올 라 갈 수 있 으 며 다음 단 계 는 현재 값 + 1 로 수정 합 니 다. 현재 좌표 로 돌아 가 위로 올 라 갈 수 없 을 때 까지 계속 앞으로 갑 니 다.
왼쪽: 올 라 가면 왼쪽 이 안 되 고 갈 수 있 는 지 판단 하면 왼쪽으로 갈 수 있 으 며 다음 단 계 는 현재 값 + 1 로 수정 합 니 다. 현재 좌표 로 돌아 가 왼쪽 으로 갈 수 없 을 때 까지 계속 왼쪽으로 갑 니 다.
오른쪽: 왼쪽 이 통 하지 않 고 오른쪽 이 통 하지 않 습 니 다. 갈 수 있 는 지 판단 하면 오른쪽으로 갈 수 있 습 니 다. 그리고 다음 단 계 는 현재 값 + 1 입 니 다. 현재 좌 표를 되 돌려 오른쪽으로 가면 안 될 때 까지 오른쪽으로 갑 니 다.
아래: 오른쪽 이 통 하지 않 고 내 려 갈 수 있 는 지 판단 하면 내 려 갈 수 있 습 니 다. 다음 단 계 는 현재 값 + 1 입 니 다. 현재 좌표 로 돌아 가 내 려 갈 수 없 을 때 까지 계속 내 려 갑 니 다.
3. 반복 과정 24. 출구 를 찾 으 면 출구 가 두 개 있 을 수 있 으 므 로 서둘러 물 러 나 서 다른 출구 가 있 는 지 찾 아야 한다. 5. 수출 의 가장 짧 은 경 로 는 주로 재 귀적 인 생각 을 사용 하고 지나 간 길 은 반복 되 지 않 는 다. 그리고 지나 간 후에 모든 값 은 > 1 의 숫자 로 변 한다.

#define ROW 6
#define COL 6
#define MAX 20


typedef int DataType;

typedef struct postion
{
    int _x;
    int _y;
}position;
typedef position SDataType;

typedef struct Stack
{
    SDataType array[MAX];
    int top;
}Stack;

typedef struct Maze
{
    DataType _map[ROW][COL];
}Maze;


void InitMaze(int map[ROW][COL],Maze* m);//   
void PrintfMaze(Maze* m);//    
void PassMaze(Maze* m, SDataType enter);//   

스 택 에 좌표 형식 을 눌 러 서 데 이 터 를 만 들 려 면 좌표 형식의 구조 체 를 만 들 고 좌표 형식 으로 스 택 의 유형 을 정의 해 야 합 니 다.

void InitMaze(int map[ROW][COL],Maze* m)//   
{
    int i = 0;
    int j = 0;
    assert(m);
    for (; i < ROW; i++)
    {
        for (j = 0; j < COL; j++)
        {
            m->_map[i][j] = map[i][j];
        }
    }

}
void PrintfMaze(Maze* m)//    
{
    int i = 0;
    int j = 0;
    assert(m);
    for (; i < ROW; i++)
    {
        for (j = 0; j < COL; j++)
            printf("%3d", m->_map[i][j]);
        printf("
");
    }
}

int IsValid(SDataType enter)//        
{
    if (0 == enter._x || 0 == enter._y || ROW - 1 == enter._x || COL - 1 == enter._y)
        return 1;
    return 0;
}

int IsExit(SDataType Cur,SDataType enter)//       
{
    if ((0 == Cur._x || 0 == Cur._y || ROW - 1 == Cur._x || COL - 1 == Cur._y) && (Cur._x != enter._x || Cur._y != enter._y)) 
        return 1;
    return 0;
}


int IsPass(Maze* m, SDataType next)//       
{
    assert(m);
    if (next._x < ROW && next._y < COL && next._x >= 0 && next._y >= 0)
    {
        if (1 == m->_map[next._x][next._y])
            return 1;
    }   
    return 0;
}
void SaveShortPath(Stack* Path, Stack* ShortPath)//      
{
    int i = 0;
    for (; i < StackSize(Path); i++)
        ShortPath->array[i] = Path->array[i];
    ShortPath->top = Path->top;
}
void _GetPassMaze(Maze* m, SDataType enter, SDataType Cur, Stack* Path, Stack* ShortPath)//  
{
    SDataType next;
    if (!StackSize(Path))//     ，            2  
        m->_map[enter._x][enter._y] = 2;
    if (IsExit(Cur, enter))//       
    {
        StackPush(Path, Cur);
        if (!StackSize(ShortPath) || StackSize(Path) < StackSize(ShortPath))
            SaveShortPath(Path, ShortPath);//      
        StackPop(Path);
        return;
    }
    StackPush(Path, Cur);
    // 
    next = Cur;
    next._x -= 1;
    if (IsPass(m, next, Cur))//         
    {
        m->_map[next._x][next._y] = m->_map[Cur._x][Cur._y] + 1;
        _GetPassMaze(m, enter, next, Path, ShortPath);
    }
    // 
    next = Cur;
    next._y -= 1;
    if (IsPass(m, next, Cur))//         
    {
        m->_map[next._x][next._y] = m->_map[Cur._x][Cur._y] + 1;
        _GetPassMaze(m, enter, next, Path, ShortPath);
    }
    // 
    next = Cur;
    next._y += 1;
    if (IsPass(m, next, Cur))//         
    {
        m->_map[next._x][next._y] = m->_map[Cur._x][Cur._y] + 1;
        _GetPassMaze(m, enter, next, Path, ShortPath);
    }
    // 
    next = Cur;
    next._x += 1;
    if (IsPass(m, next, Cur))//         
    {
        m->_map[next._x][next._y] = m->_map[Cur._x][Cur._y] + 1;
        _GetPassMaze(m, enter, next, Path, ShortPath);
    }
    StackPop(Path);
}

void PassMaze(Maze* m, SDataType enter)
{
    Stack ShortPath;
    Stack Path;
    assert(m);
    InitStack(&Path);
    InitStack(&ShortPath);
    if (!IsValid(enter))
        return;
    _GetPassMaze(m, enter, enter, &Path, &ShortPath);//      ，   

}

void Test()//    
{
    SDataType enter;
    Maze m;
    int map[ROW][COL] = {   0,0,0,0,0,0,
                            0,0,1,0,0,0,
                            0,0,1,0,0,0,
                            0,0,1,0,0,0,
                            0,0,1,1,1,1,
                            0,0,1,0,0,0 };
    InitMaze(map,&m);
    PrintfMaze(&m);
    printf("
");
    enter._x = 5;
    enter._y = 2;
    PassMaze(&m, enter);
    PrintfMaze(&m);
}

위의 이 코드 는 몇 개의 스 택 의 기본 함수 가 주지 않 아서 스스로 완벽 하 게 호출 할 수 있 습 니 다.