搜索算法之迷宫问题

迷宫问题

Description

  给定一个n×m方格的迷宫，迷宫里有t处障碍，障碍处不可通过。给定起点坐标和终点坐标，问每个方格最多经过1次，在迷宫中移动有上下左右四种方式，保证起点上没有障碍。问：
  ① 有多少种从起点坐标到终点坐标的方案？
  ② 从起点到终点的最短路径长度是多少？输出一条长度最短的路径经过的点的坐标，若不

存在起点到终点的路径，则输出-1.

Input

第一行n、m和t，其中：n为行数，m为列数，t为障碍数。
第二行起点坐标sx、sy，终点坐标ex、ey。
接下来t行，每行为障碍的坐标。

Output

第一行从起点坐标到终点坐标的方案总数。
若存在解答，则第二行输出最短路径的长度len（起点和终点也算在步数内），以下len行，每行输出经过点的坐标（i, j）；
否则无解时输出-1

Sample Input

4 5 4
0 0 3 4
0 2
1 1
2 3
3 1

Sample Output

3
8
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(3, 2)
(3, 3)
(3, 4)

analysis

  使用深搜和广搜

Source Code

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 150
int map[MAX][MAX],book[MAX][MAX],path[MAX][2];  //地图和标记 
int n,m,t,sx,sy,ex,ey;              //行、列、障碍数、起点坐标、终点坐标 
int num=0;                          //方案总数 
int dir[4][2]={
    {0, 1},                         //右 
    {1, 0},                         //下 
    {0,-1},                         //左 
    {-1,0},                         //上 
};
struct Node{                        //队列 
    int x;
    int y;
    int len;
    int f;
}Queue[MAX];
int head,tail;                      //队列的头尾指针 

int go(int x, int y)
{
    if (x<0 || x>=n || y<0 || y>=m)
        return 0;
    else 
        return 1;
}
void dfs(int x, int y)
{
    int nx,ny;
    if (x==ex && y==ey)
    {
        num++;return ;
    }
    for (int k=0; k<4; k++)
    {
        nx=x+dir[k][0]; ny=y+dir[k][1];
        if (go(nx, ny)==1 && map[nx][ny]==0 &&book[nx][ny]==0)
        {
            book[nx][ny]=1;
            dfs(nx, ny);
            book[nx][ny]=0;
        }
    }
    return ;
}
void bfs(int x, int y)
{
    int nx,ny;
    for (int k=0; k<4; k++)
    {
        nx=x+dir[k][0]; ny=y+dir[k][1];
        if (go(nx, ny)==1 && map[nx][ny]==0 &&book[nx][ny]==0)
        {
            Queue[tail].x=nx;
            Queue[tail].y=ny;
            Queue[tail].len=Queue[head].len+1;
            Queue[tail].f=head;
            tail++;
            book[nx][ny]=1;
            if (nx==ex && ny==ey)
                return ;
        }
    }
    head++;
    bfs(Queue[head].x, Queue[head].y);

}
int main()
{
    int tx,ty,t;                    //用于临时存储坐标 
    int i,j;
    int len;
    memset(book, 0, sizeof(book));
    memset(path, 0, sizeof(path));
    //freopen("test.in","r",stdin);
    scanf("%d %d %d", &n, &m, &t);
    scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
    for (i=0; i<t; i++)
    {
        scanf("%d %d", &tx, &ty);
        map[tx][ty]=1;  
    }
    book[sx][sy]=1;
    dfs(sx, sy);

    memset(book, 0, sizeof(book));      //初始化标记和头尾指针 
    head=tail=0;
    Queue[tail].x=sx;
    Queue[tail].y=sy;
    Queue[tail].len=1;
    Queue[tail].f=0;
    tail++;
    printf("%d\n", num);
    bfs(sx, sy);
    len=Queue[--tail].len;
    printf("%d\n", len);
    i=tail;
    j=len-1;
    path[j][0]=ex;path[j][1]=ey;
    j--;
    while (i>1)
    {
        t=Queue[tail].f;
        path[j][0]=Queue[t].x;
        path[j][1]=Queue[t].y;
        tail=t;
        i--;j--;
    }
    for (j=0; j<len; j++)
        printf("(%d,%d)\n", path[j][0], path[j][1]);
    //fclose(stdin);
    return 0;
}