首页 > 代码库 > FOJ1205 小鼠迷宫问题 (BFD+递推)

FOJ1205 小鼠迷宫问题 (BFD+递推)

2024-09-02 05:57:59   211人阅读

FOJ1205 小鼠迷宫问题 (BFD+递推)

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

 

 

图 小鼠的迷宫

编程任务：

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

 

INPUT：

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

 

OUTPUT:

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

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

input.txt

output.txt

8 8 3

3 3

4 5

6 6

2 1

7 7

11

96

解题报告

看到这个题目，首先给人的第一感觉就是用BFS。初始障碍不能走为-1，一个点向四周扩散。 在数组g上保留广搜的痕迹，即走到每个格子的最短距离。至于路径条数，可以用递推来求。如果一个格子的相邻为其距离减一，即代表这个格子可由其走到。故其方案数为其四周满足的格子的方案数总和。初始起点为1.输出终点即可。算法复杂度为O(n+m)

 

附上代码

#include<bits/stdc++.h>#define Pair pair<int,int>#define MAXN 100000+1#define MAXM 2000000+1using namespace std;int g[80][80],ans[80][80],n,m,k,s1,s2,e1,e2,qq;struct Data{    int x,y,dis;};Data make(int x,int y,int dis){    Data j;j.x=x;j.y=y;j.dis=dis;    return j;}void bfs(){    queue <Data> h;    Data temp;temp.x=s1;temp.y=s2;temp.dis=1;    g[s1][s2]=1;    h.push(temp);    while(h.size()>0)    {        Data t=h.front();h.pop();                if(t.x>1&&g[t.x-1][t.y]!=-1&&g[t.x-1][t.y]==0)         {h.push(make(t.x-1,t.y,t.dis+1));g[t.x-1][t.y]=t.dis+1;}                if(t.y>1&&g[t.x][t.y-1]!=-1&&g[t.x][t.y-1]==0)         {h.push(make(t.x,t.y-1,t.dis+1));g[t.x][t.y-1]=t.dis+1;}                if(t.x<n&&g[t.x+1][t.y]!=-1&&g[t.x+1][t.y]==0)         {h.push(make(t.x+1,t.y,t.dis+1));g[t.x+1][t.y]=t.dis+1;}                if(t.y<m&&g[t.x][t.y+1]!=-1&&g[t.x][t.y+1]==0)         {h.push(make(t.x,t.y+1,t.dis+1));g[t.x][t.y+1]=t.dis+1;}        if(g[e1][e2]!=0)         {            printf("%d\n",g[e1][e2]-1);            break;        }    }}int answer(int x,int y){    if(ans[x][y]==0)    {    int a=0,b=0,c=0,d=0;        if(g[x-1][y]+1==g[x][y]) a=answer(x-1,y),ans[x][y]+=a,a=0;                        if(g[x][y-1]+1==g[x][y]) b=answer(x,y-1),ans[x][y]+=b,b=0;                        if(g[x+1][y]+1==g[x][y]) c=answer(x+1,y),ans[x][y]+=c,c=0;                if(g[x][y+1]+1==g[x][y]) d=answer(x,y+1),ans[x][y]+=d,d=0;                return ans[x][y];    }else    return ans[x][y];}int main(){    scanf("%d%d%d",&n,&m,&k);    for(int i=1;i<=k;i++)    {        int x,y;        scanf("%d%d",&x,&y);        g[x][y]=-1;    }    scanf("%d%d%d%d",&s1,&s2,&e1,&e2);    bfs();    ans[s1][s2]=1;    answer(e1,e2);    printf("%d\n",ans[e1][e2]);    return 0;}

 

FOJ1205 小鼠迷宫问题 (BFD+递推)


联系
我们