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

解题报告

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

附上代码

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