问题描述

给定一个迷宫（二维数组），其中 0 表示通路，1 表示墙壁，S 表示起点，E 表示终点。需要找出一条从起点到终点的路径。

1、深度优先搜索（DFS）

深度优先搜索是一种用于遍历或搜索树或图的算法。它沿着树的深度遍历节点，尽可能深的搜索分支节点。

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

#define ROW 4
#define COL 4

int maze[ROW][COL] = {
    { 'S', 0, 1, 0 },
    { 0, 0, 1, 0 },
    { 1, 0, 0, 'E' },
    { 1, 1, 0, 1 }
};

int dir[4][2] = {
    { -1, 0 },
    { 1, 0 },
    { 0, -1 },
    { 0, 1 }
};

bool isValid(int x, int y) {
    return (x >= 0 && x < ROW && y >= 0 && y < COL && (maze[x][y] == 0 || maze[x][y] == 'E'));
}

bool dfs(int x, int y) {
    if (maze[x][y] == 'E') {
        return true;
    }

    maze[x][y] = -1;

    for (int i = 0; i < 4; i++) {
        int newX = x + dir[i][0];
        int newY = y + dir[i][1];

        if (isValid(newX, newY) && dfs(newX, newY)) {
            return true;
        }
    }

    maze[x][y] = 0;
    return false;
}

int main() {
    int startX, startY;

    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++) {
            if (maze[i][j] == 'S') {
                startX = i;
                startY = j;
                break;
            }
        }
    }

    if (dfs(startX, startY)) {
        printf("找到一条从起点到终点的路径。\n");
    } else {
        printf("没有找到从起点到终点的路径。\n");
    }

    return 0;
}

2、广度优先搜索（BFS）

广度优先搜索是一种用于遍历或搜索树或图的算法。它从树的根节点开始，沿着树的宽度遍历节点。

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

#define ROW 4
#define COL 4

typedef struct {
    int x, y;
} Point;

typedef struct {
    Point *data;
    int front, rear, size, capacity;
} Queue;

Queue* createQueue(int capacity) {
    Queue *queue = (Queue *)malloc(sizeof(Queue));
    queue->capacity = capacity;
    queue->front = queue->size = 0;
    queue->rear = capacity - 1;
    queue->data = (Point *)malloc(queue->capacity * sizeof(Point));
    return queue;
}

bool isFull(Queue *queue) {
    return (queue->size == queue->capacity);
}

bool isEmpty(Queue *queue) {
    return (queue->size == 0);
}

void enqueue(Queue *queue, Point item) {
    if (isFull(queue))
        return;
    queue->rear = (queue->rear + 1) % queue->capacity;
    queue->data[queue->rear] = item;
    queue->size = queue->size + 1;
}

Point dequeue(Queue *queue) {
    if (isEmpty(queue)) {
        Point p = {-1, -1};
        return p;
    }
    Point item = queue->data[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;
    queue->size = queue->size - 1;
    return item;
}

int maze[ROW][COL] = {
    { 'S', 0, 1, 0 },
    { 0, 0, 1, 0 },
    { 1, 0, 0, 'E' },
    { 1, 1, 0, 1 }
};

int dir[4][2] = {
    { -1, 0 },
    { 1, 0 },
    { 0, -1 },
    { 0, 1 }
};

bool isValid(int x, int y) {
    return (x >= 0 && x < ROW && y >= 0 && y < COL && (maze[x][y] == 0 || maze[x][y] == 'E'));
}

bool bfs(int startX, int startY) {
    Queue *queue = createQueue(ROW * COL);
    Point start = {startX, startY};
    enqueue(queue, start);
    maze[startX][startY] = -1;

    while (!isEmpty(queue)) {
        Point curr = dequeue(queue);
        if (maze[curr.x][curr.y] == 'E') {
            return true;
        }

        for (int i = 0; i < 4; i++) {
            int newX = curr.x + dir[i][0];
            int newY = curr.y + dir[i][1];

            if (isValid(newX, newY)) {
                Point next = {newX, newY};
                enqueue(queue, next);
                maze[newX][newY] = -1;
            }
        }
    }

    return false;
}

int main() {
    int startX, startY;

    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++) {
            if (maze[i][j] == 'S') {
                startX = i;
                startY = j;
                break;
            }
        }
    }

    if (bfs(startX, startY)) {
        printf("找到一条从起点到终点的路径。\n");
    } else {
        printf("没有找到从起点到终点的路径。\n");
    }

    return 0;
}

3、递归回溯法

递归回溯法是一种探索所有可能路径的算法，适用于求解迷宫等问题。

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

#define ROW 4
#define COL 4

int maze[ROW][COL] = {
    { 'S', 0, 1, 0 },
    { 0, 0, 1, 0 },
    { 1, 0, 0, 'E' },
    { 1, 1, 0, 1 }
};

int dir[4][2] = {
    { -1, 0 },
    { 1, 0 },
    { 0, -1 },
    { 0, 1 }
};

bool isValid(int x, int y) {
    return (x >= 0 && x < ROW && y >= 0 && y < COL && (maze[x][y] == 0 || maze[x][y] == 'E'));
}

bool backtrack(int x, int y) {
    if (maze[x][y] == 'E') {
        return true;
    }

    maze[x][y] = -1;

    for (int i = 0; i < 4; i++) {
        int newX = x + dir[i][0];
        int newY = y + dir[i][1];

        if (isValid(newX, newY) && backtrack(newX, newY)) {
            return true;
        }
    }

    maze[x][y] = 0;
    return false;
}

int main() {
    int startX, startY;

    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++) {
            if (maze[i][j] == 'S') {
                startX = i;
                startY = j;
                break;
            }
        }
    }

    if (backtrack(startX, startY)) {
        printf("找到一条从起点到终点的路径。\n");
    } else {
        printf("没有找到从起点到终点的路径。\n");
    }

    return 0;
}