C语言DFS和BFS解决迷宫问题

C语言DFS与BFS

迷宫问题

题目描述

给定一个 N \times MN×M 方格的迷宫，迷宫里有 TT 处障碍，障碍处不可通过。

在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。

给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。

输入格式

第一行为三个正整数 N,M,TN,M,T，分别表示迷宫的长宽和障碍总数。

第二行为四个正整数 SX,SY,FX,FYSX,SY,FX,FY，SX,SYSX,SY 代表起点坐标，FX,FYFX,FY 代表终点坐标。

接下来 TT 行，每行两个正整数，表示障碍点的坐标。

输出格式

输出从起点坐标到终点坐标的方案总数。

解题思路

这个问题，方案总数的话还是要用DFS（深度搜索优先）。深搜是一条路走到黑，不撞南墙不回头。需要一个二维数组记下走过的或者不能走的（这里指障碍），我们把这些情况在book数组里面统统记作1（没走用0表示），然后就是每一次递归我们都确定一个坐标。如何确定呢，就是每一个都试一试（上下左右），看满不满足条件（条件是不为1）。满足然后往下递归，记得book数组对应记1。这里有一个很重要的点（这里采用的是回溯算法），递归回来的时候我们要把这个点当作它没有出现继续试试另外的路（就是把book记为0）。结束递归，就是判断当前坐标是否到了终点坐标，用全局变量记数（当然你也可以把它加入函数参数来每次递归计数）。

最短路径这个问题就得看BFS（广度搜素优先）。这个是每一个坐标都试一次，把所有出现的情况都记下来。这个算法牵扯到队列，这也是利用队列先进先出的特点来做。我们定义一个结构体里面包含x，y的坐标，还有s（从开始到这要走的步数），这个结构体我们定义M*N+1大小的队列（为什么是+1因为这是要判断结束的条件，而且最多就是M*N个，因为每一个只找一次），从head开始记录起始坐标，tail则到head后面去，用来保留要存进去的坐标。我们同样用book数组来记录是否出现或者是障碍。我们从当前坐标能走开始（上下左右），按照你想要的顺序来。然后看它是否满足条件（遇到障碍或者走过也就是1的情况），满足记录下来，我们要把这个坐标所有能延生的点都记录下来，tail记录之后++，记得s也要在head的s的基础上+1（从head延生的，当然要+1，走了一步了），book要记下来走过了，这跟深搜不一样，广搜每一个点之走一次，所以没关系。这个坐标举完了之后要记得head++，head就到下一个能够延生的坐标了，在在这个点继续延生。在其中我们判断是否到达了终点坐标，第一次到的一定是最短路径，这个因为，是最短才会最快出现。这个时候记录下来当前tail的s的值，break即可。

#include<stdio.h>
#include<malloc.h>
#define N 5
#define M 5
int book[M][N]={0},count=0;
int start[2]={0},end[2]={0};
int dfs(int x,int y)
{
	int i,j,tx,ty;
	if(x==end[0]&&y==end[1])
	{
		count++;
		return 0;
	}
	
	int k[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
	for(i=0;i<4;i++)
	{
		tx=x+k[i][0];ty=y+k[i][1];
		if(tx>=1&&tx<=m&&ty>=1&&ty<=n)
			if(book[tx][ty]==0)
			{
				book[tx][ty]=1;
				dfs(tx,ty);
				book[tx][ty]=0;
			}
	}
}

typedef struct node
{
    int x;
    int y;
    int s;
    
}NODE; 
NODE que[M*N+1];
int head=1,tail=2,min=M*N;
int bfs()
{
    int k[4][2]={{-1,0},{0,1},{1,0},{0,-1}},flag=0;
    int i,j,tx,ty;
    while(head<tail)
    {
        for(i=0;i<4;i++)
        {
            tx=que[head].x+k[i][0];
            ty=que[head].y+k[i][1];
            if(tx>=start[0]&&tx<=end[0]&&ty>=start[1]&&ty<=end[1])
                if(book[tx][ty]==0)
                {
                    que[tail].x=tx;
                    que[tail].y=ty;
                    que[tail].s=que[head].s+1;
                    if(tx==end[0]&&ty==end[1])
                        if(min>que[tail].s) 
                        {
                            min=que[tail].s;
                            flag=1;
                            break;
                        }
                    tail++;
                    book[tx][ty]=1;
                }
            
        }
        if(flag==1) break;
        head++;
    }
}
int main() 
{
    int m,n,t,i,j,x,y;//第一个输入的是长，第二个是宽
    scanf("%d%d%d",&n,&m,&t);//我习惯用m表示行，n表示列
    scanf("%d%d%d%d",&start[0],&start[1],&end[0],&end[1]);
    for(i=0;i<t;i++)
    {
        scanf("%d%d",&x,&y);
        book[x][y]=1;
    }    
    dfs(start[0],start[1]);
    que[1].x=start[0];
    que[1].y=start[1];
    que[1].s=0;    
    bfs();
    printf("the min is%d\n",min);
    printf("the total is%d\n",count);
    return 0;
}