题解 | #迷宫问题# 一直往右走即可走出迷宫+栈的思想

因为只有且仅有一条路能走出迷宫，那就用最简单，从自己的最右边一直走。最后就能走出迷宫了。

为每个点都设置5个标志，四个方向是否可以走的标志，入口方向标志。

设置一个数组栈，把第一个点作为入口，加入栈低。最up标志开始（即自己的右边开始），把能走的点都加入到栈中，当走到死胡同时，就出栈，在出栈的过程中，把死胡同做上"1"的标记，这样，在出栈的时候，对每个点的标志进行判定，能走的点，继续入栈，否则，继续出栈。当终点入栈，则栈就是我们用这个方法走出的一条起点到终点的路径。

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef enum { UP = 1, RIGHT, DOWN, LEFT, ZERO } Entry_e;

typedef struct {
    int  pos_row;
    int  pos_col;
    int  entry;
    bool up;
    bool down;
    bool right;
    bool left;
} Node_t;

int **new_array(int row, int col)
{
    int **array = calloc(row, sizeof(int *));
    for (int i = 0; i < row; i++) {
        array[i] = calloc(col, sizeof(int));
    }
    return array;
}

void delete_array(int **array, int row)
{
    for (int i = 0; i < row; i++) {
        free(array[i]);
    }
    free(array);
}

void get_nums(int **array, int row, int col)
{
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            scanf("%d", &array[i][j]);
        }
    }
}

void print_nums(int **array, int row, int col)
{
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            printf("%d ", array[i][j]);
        }
        printf("\n");
    }
}

bool is_in_table(int pos_row, int pos_rol, int **array, int row, int rol)
{
    if (pos_row >= 0 && pos_row < row && pos_rol >= 0 && pos_rol < rol) {
        if (array[pos_row][pos_rol] != 1) {
            return true;
        }
    }
    return false;
}

void scan_around(Node_t *node, int **array, int rowMax, int colMax)
{
    int row           = node->pos_row;
    int col           = node->pos_col;
    int pos_up_row    = row - 1;
    int pos_up_col    = col;
    int pos_down_row  = row + 1;
    int pos_down_col  = col;
    int pos_right_row = row;
    int pos_right_col = col + 1;
    int pos_left_row  = row;
    int pos_left_col  = col - 1;
    node->up          = is_in_table(pos_up_row, pos_up_col, array, rowMax, colMax);
    node->down        = is_in_table(pos_down_row, pos_down_col, array, rowMax, colMax);
    node->right       = is_in_table(pos_right_row, pos_right_col, array, rowMax, colMax);
    node->left        = is_in_table(pos_left_row, pos_left_col, array, rowMax, colMax);
}

void print_node(Node_t *node)
{
    printf("row:%d, col:%d, entry:%d\n", node->pos_row, node->pos_col, node->entry);
    printf("up:%d, right:%d, down:%d, left:%d\n", node->up, node->right, node->down, node->left);
}

bool traverse(int **array, int row, int col, Node_t *nodes, int *index)
{
    Node_t *node = &nodes[*index];
    // print_node(node);
    if (node->entry != UP && node->up) {
        if (array[node->pos_row - 1][node->pos_col] == 0) {
            (*index)++;
            Node_t *nn  = &nodes[*index];
            nn->entry   = DOWN;
            nn->pos_row = node->pos_row - 1;
            nn->pos_col = node->pos_col;
            scan_around(nn, array, row, col);
        }
    } else if (node->entry != RIGHT && node->right) {
        if (array[node->pos_row][node->pos_col + 1] == 0) {
            (*index)++;
            Node_t *nn  = &nodes[*index];
            nn->entry   = LEFT;
            nn->pos_row = node->pos_row;
            nn->pos_col = node->pos_col + 1;
            scan_around(nn, array, row, col);
        }
    } else if (node->entry != DOWN && node->down) {
        if (array[node->pos_row + 1][node->pos_col] == 0) {
            (*index)++;
            Node_t *nn  = &nodes[*index];
            nn->entry   = UP;
            nn->pos_row = node->pos_row + 1;
            nn->pos_col = node->pos_col;
            scan_around(nn, array, row, col);
        }
    } else if (node->entry != LEFT && node->left) {
        if (array[node->pos_row][node->pos_col - 1] == 0) {
            (*index)++;
            Node_t *nn  = &nodes[*index];
            nn->entry   = RIGHT;
            nn->pos_row = node->pos_row;
            nn->pos_col = node->pos_col - 1;
            scan_around(nn, array, row, col);
        }
    } else {
        array[node->pos_row][node->pos_col] = 1;
        (*index)--;
        Node_t *nn = &nodes[*index];
        scan_around(nn, array, row, col);
    }

    // print_path(nodes, *index);
    // printf("--------------------------------\n\n");
    // sleep(1);

    if (nodes[*index].pos_row == row - 1 && nodes[*index].pos_col == col - 1) {
        return true;
    }
    return false;
}

void print_path(Node_t *nodes, int index)
{
    for (int i = 0; i <= index; i++) {
        printf("(%d,%d)\n", nodes[i].pos_row, nodes[i].pos_col);
    }
}

int main()
{
    int row = 0;
    int col = 0;
    while (scanf("%d %d", &row, &col) != EOF) {
        int **array = new_array(row, col);
        get_nums(array, row, col);
        // print_nums(array, row, col);

        Node_t *nodes    = calloc(row * col, sizeof(Node_t));
        int     index    = 0;
        nodes[0].entry   = ZERO;
        nodes[0].pos_row = 0;
        nodes[0].pos_col = 0;
        scan_around(&nodes[0], array, row, col);

        while (!traverse(array, row, col, nodes, &index)) {
            ;
        }

        print_path(nodes, index);
        delete_array(array, row);
    }
    return 0;
}