迷宫中级版（路径的条数）【问题描述】下图给出了一个迷宫的平面图，其中标记为黑色的为障碍，标记为白色的为可以通行的区域。迷宫的入口为左上角的黄色方格，出口为右下角的黄色方格

【问题描述】下图给出了一个迷宫的平面图，其中标记为黑色的为障碍，标记为白色的为可以通行的区域。迷宫的入口为左上角的黄色方格，出口为右下角的黄色方格。在迷宫中，只能从一个方格走到相邻的上、下、左、右四个方向之一。

找到迷宫从起点到终点的所有路径，输出路径条数。如果从起点到终点没有路径，则输出NO PASS!

注：所有迷宫的起点为左上角，终点为右下角。

【输入形式】依次输入n行由0和1构成的字符串，每行字符串长度相同，输入空串结束，其中1表示围墙，0表示可行路径。
【输出形式】如果起点到终点有路，则路径的条数；否则输出NO PASS!。
【样例输入】
0101101
0000001
1001101
0010001
1010101
0000000
【样例输出】
8
【样例说明】
迷宫总共有8条路径：
DRDDDDRRRRR
DRDDDDRRUURRDDR
DRDRURRRDDDDR
DRDRURRRDDLLDDRRR
DRRDLDDDRRRRR
DRRDLDDDRRUURRDDR
DRRRRRDDDDR
DRRRRRDDLLDDRRR
所以输出数字8

答案：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int count = 0;
#define MAX 120
void dfs(int x, int y);
int row = 0;
int col = 0;
int **mark = NULL;
int maze[MAX][MAX];
// 定义方向数组 上，下，左，右
int direction[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// 深度优先搜索数据
int main()
{
? ? char str[MAX + 1];
? ? while (fgets(str, MAX + 2, stdin) != NULL)
? ? {
? ? ? ? if (str[0] == '\n')
? ? ? ? {
? ? ? ? ? ? break;
? ? ? ? }
? ? ? ? col = strlen(str) - 1;
? ? ? ? for (int j = 0; j < col; j++)
? ? ? ? {
? ? ? ? ? ? maze[row][j] = str[j] - '0';
? ? ? ? }
? ? ? ? row++;
? ? }
? ? mark = (int **)malloc(row * sizeof(int *));
? ? for (int i = 0; i < row; i++)
? ? {
? ? ? ? mark[i] = (int *)malloc(col * sizeof(int));
? ? ? ? memset(mark[i], 0, col * sizeof(int));
? ? }
? ? mark[0][0] = 1;
? ? dfs(0, 0);

? ? // 判断是否找到出口
? ? if (count == 0)
? ? {
? ? ? ? printf("NO PASS!\n");
? ? }
? ? else
? ? {
? ? ? ? printf("%d\n", count);
? ? }
? ? free(mark);
? ? system("pause");
? ? return 0;
}

void dfs(int x, int y)
{
? ? char path[MAX];
? ? int len = 0;
? ? if (x == row - 1 && y == col - 1)
? ? {
? ? ? ? // ? printf("%d,%d\n", x, y);
? ? ? ? count++;
? ? ? ? // mark[row - 1][col - 1] = 1;
? ? ? ? return;
? ? }
? ? else
? ? {
? ? ? ? // 否则按照顺序依次尝试四个方向
? ? ? ? for (int i = 0; i < 4; i++)
? ? ? ? {
? ? ? ? ? ? int next_x = x + direction[i][0];
? ? ? ? ? ? int next_y = y + direction[i][1];
? ? ? ? ? ? if (next_x < 0 || next_x >= row || next_y < 0 || next_y >= col)
? ? ? ? ? ? ? ? continue;
? ? ? ? ? ? if (mark[next_x][next_y] == 1 || maze[next_x][next_y] == 1)
? ? ? ? ? ? ? ? continue;

? ? ? ? ? ? /* ? ? ?switch (i)
? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? case 0:
? ? ? ? ? ? ? ? ? ? ? putchar('U');
? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? ? case 1:
? ? ? ? ? ? ? ? ? ? ? putchar('D');
? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? ? case 2:
? ? ? ? ? ? ? ? ? ? ? putchar('L');
? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? ? case 3:
? ? ? ? ? ? ? ? ? ? ? putchar('R');
? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? ? }*/
? ? ? ? ? ? // 标记当前位置已走过
? ? ? ? ? ? mark[next_x][next_y] = 1;
? ? ? ? ? ? // 继续往下搜素
? ? ? ? ? ? dfs(next_x, next_y);
? ? ? ? ? ? if (mark[row - 1][col - 1] == 1)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? /*path[len] = '\0';
? ? ? ? ? ? ? ? printf("%s", path);
? ? ? ? ? ? ? ? return;*/
? ? ? ? ? ? }

? ? ? ? ? ? // 如果找不到出口则撤销标记
? ? ? ? ? ? mark[next_x][next_y] = 0;
? ? ? ? }
? ? }
}