[两只老鼠跑得快]小鼠迷宫问题

时间：2010-09-15 来源：Sephiroth Lee

【描述】

小鼠a与小鼠b身处一个m×n的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这m×n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿上，下，左，右4个方向进入未封闭的房间。小鼠a位于迷宫的(p，q)方格中，它必须找出一条通向小鼠b所在的(r，s)方格的路。请帮助小鼠a找出所有通向小鼠b的最短道路。

对于给定的小鼠的迷宫，编程计算小鼠a通向小鼠b的所有最短道路。

【输入格式】

由文件input.txt给出输入数据。第一行有3个正整数n，m，k，分别表示迷宫的行数，列数和封闭的房间数。接下来的k行中，每行2个正整数，表示被封闭的房间所在的行号和列号。最后的2行，每行也有2个正整数，分别表示小鼠a所处的方格(p，q)和小鼠b所处的方格(r，s)。

【输出格式】

将计算出的小鼠a通向小鼠b的最短路长度和有多少条不同的最短路输出到文件output.txt。文件的第一行是最短路长度。文件的第2行是不同的最短路数。

如果小鼠a无法通向小鼠b则输出“NoSolution!”。

【样例输入】

8 8 3

3 3

4 5

6 6

2 1

7 7

【样例输出】

【分析】

f[i][j].dis代表到i,j这个点的最短路径。f[i][j].count代表最短路径的条数。然后SPFA就可以了啊。

#include <stdio.h>
#define maxn 1001
#define MAXINT 1000000000

bool have[maxn][maxn];
struct tt
{
    int dis,count;
} f[maxn][maxn];
struct ss
{
    int x,y;
} q[maxn*100];
int l,r;
int sx,sy,ex,ey;
int n,m;
bool v[maxn][maxn];
int tx,ty,nx,ny,k;
int xx[4]={1,-1,0,0};
int yy[4]={0,0,1,-1};

bool inmap(int x,int y)
{
    return ((x>0)&&(x<=n)&&(y>0)&&(y<=m));
}

int main()
{
    freopen("maze.in","r",stdin);
    freopen("maze.out","w",stdout);
    
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1;i<=k;++i)
    {
        scanf("%d%d",&tx,&ty);
        have[tx][ty]=1;
    }
    scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
    q[0].x=sx;
    q[0].y=sy;
    v[sx][sy]=1;
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j)
            f[i][j].dis=MAXINT;
    f[sx][sy].dis=0;
    f[sx][sy].count=1;
    while (l<=r)
    {
        tx=q[l].x;
        ty=q[l].y;
        for (int i=0;i<4;++i)
        {
            nx=tx+xx[i];
            ny=ty+yy[i];
            if (!inmap(nx,ny)) continue;
            if (have[nx][ny]) continue;
            if (f[tx][ty].dis+1<f[nx][ny].dis)
            {
                f[nx][ny].dis=f[tx][ty].dis+1;
                f[nx][ny].count=f[tx][ty].count;
                if (!v[nx][ny])
                {
                    q[++r].x=nx;
                    q[r].y=ny;
                    v[nx][ny]=1;
                }
            }
            else
                if (f[tx][ty].dis+1==f[nx][ny].dis)
                {
                    f[nx][ny].count+=f[tx][ty].count;
                    if (!v[nx][ny])
                    {
                        q[++r].x=nx;
                        q[r].y=ny;
                        v[nx][ny]=1;
                    }
                }
        }
        v[tx][ty]=0;
        ++l;
    }
    if (f[ex][ey].dis<MAXINT) printf("%d\n%d\n",f[ex][ey].dis,f[ex][ey].count);
    else printf("No Solution!\n");
    return 0;
}