营救(rescue)
【问题描述】 dst被fls绑架了！ fls家的俯视图是一个n×m的长方形。我们定义第i行第j列的坐标为(i,j)。 dst目前处于 (sx,sy)，而fls的家门在(tx,ty)。可惜dst没有钥匙，因此只能通过 到达dst的同学xhr为他挖的地道(px,py)来逃离。同时，由于fls的家被赋予了计 算机buff，任何人只能向上、下、左、右的方向移动。形式化地讲，假设dst处 于(x,y)的位置，则他可以向(x+1,y)或(x−1,y)或(x,y+1)或(x,y−1)移动。 我们定义每一次移动为走一步路。当然fls早就想到dst会逃离，在家中设置了若 干障碍。若某点被设置了障碍，则任何人都不能到达该点。 然而，dst不知道的是，他原本想去的那个地道早已被fls摧毁。不过巧的是， dst的同学ℎc得到了fls的家门钥匙（匪夷所思）。在得到消息后，ℎc第一时间赶 到了fls的家门口。ℎc知道dst会走最短的路到达地道。因此，ℎc需要走最短的路 到达dst即将行走的路径中的任意一点（包括起点和终点）。那么请问，ℎc最少需 要走多少步路才能达到目的，成功营救dst？ 最后，dst为大家补充了最短的路的定义：对于每条路径，dst都会将他走的 每一步的方向连成一个数，其中上代表1，右代表2，下代表3，左代表4。例如 在一条路径中，他的行走方向分别是上(1)→左(4)→下(3)→上(1)→右(2)。那么 它连成的数是 14312。在所有路径中，连成的数最小的，即为最短的路。
千灯看到这道题有一个疑问。。
fls是不是指某个人(FJJ)？？？。。
千灯觉得是的(背后一凉)。
千灯十分自信的打bfs发现了问题：
dst的最短路径怎么走？
其实很简单--
我们知道bfs是将q[front]的方案进行拓展加入队尾中
所以有序的将front的方案经行拓展得到的结果也是有序的
最短路径的顺序就是：上 右 下 左
那么按照这种顺序丢入队尾得到的结果也肯定是有序的，即第一次得到的结果是最短路径
实际操作来看(上 右 下 左=1 2 3 4)111优于112，123优于132
我们知道：bfs可以看成一棵树，那么这种顺序的拓展如图：
这种图必定保证每个父节点下面的点是顺序的（从左到右）
而且按照bfs的运算方式，{S,1,1}这条路是最早被扫到的
其次是{S,1,4},再是{S,2,1}
这也保证了“最短路”的方案
千灯完成了这个阶段又开始了新的懵逼？？！：
题目明显要先求dst的路段并且标记，而且再用bfs走一遍直到碰到标记点
怎么标记呢？？
肯定有好方法dfs是不错的。
怎么dfs呢？？？！
上面讲了bfs是一棵树，那么我们可以在找到终点时，通过该点的父亲来找回到S点(Start)
如图：
这样的关系通过father[ ][ ]记录即可实现
然后用dfs对点的父亲进行搜索，直到找到S点为止
因为数据范围有限定，所以这样不会爆炸
附上AC代码不难写：
#include<bits/stdc++.h>
using namespace std;
int f,r,n,m,sx,sy,tx,ty,px,py,nextx[4]={0,1,0,-1},nexty[4]={-1,0,1,0},q[1000010][3];
bool MAP[1010][1010],second_MAP[1010][1010],v[1010][1010];
inline int get_in()
{
int x=0;int f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
struct note
{
int last_x,last_y;
}father[1010][1010];
void initialization()
{
for(int i=1;i<=n;i++) MAP[i][0]=true,MAP[i][m+1]=true;
for(int i=0;i<=m+1;i++) MAP[0][i]=true,MAP[n+1][i]=true;
}
void dfs(int do_x,int do_y)
{
if(do_x!=sx||do_y!=sy)
{
second_MAP[do_x][do_y]=true;
dfs(father[do_x][do_y].last_x,father[do_x][do_y].last_y);
}
return;
}
int main()
{
n=get_in(),m=get_in(),sx=get_in(),sy=get_in();
tx=get_in(),ty=get_in(),px=get_in(),py=get_in();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int k=get_in();
if(k==1) MAP[i][j]=true;
else MAP[i][j]=false;
}
initialization();
memset(v,0,sizeof(v));
f=r=1;
q[1][0]=sx,q[1][1]=sy,q[1][2]=0,v[sx][sy]=true;
while(f<=r)
{
int x=q[f][0],y=q[f][1];
if(x==px&&y==py)
{
second_MAP[sx][sy]=true;
dfs(x,y);
break;
}
for(int i=0;i<=3;++i)
{
int xx=x+nexty[i],yy=y+nextx[i];
if(MAP[xx][yy]==false&&v[xx][yy]==false)
{
v[xx][yy]=true;
++r,q[r][0]=xx,q[r][1]=yy,q[r][2]=q[f][2]+1;
father[xx][yy].last_x=x;
father[xx][yy].last_y=y;
}
}
++f;
}
memset(v,0,sizeof(v));
f=r=1;
q[1][0]=tx,q[1][1]=ty,q[1][2]=0,v[tx][ty]=true;
while(f<=r)
{
int x=q[f][0],y=q[f][1];
if(second_MAP[x][y]==true)
{
cout<<q[f][2];
return 0;
}
for(int i=0;i<=3;++i)
{
int xx=x+nexty[i],yy=y+nextx[i];
if(MAP[xx][yy]==false&&xx<=n&&xx>=1&&yy<=m&&yy>=1&&v[xx][yy]==false)
v[xx][yy]=true,++r,q[r][0]=xx,q[r][1]=yy,q[r][2]=q[f][2]+1;
}
++f;
}
cout<<"-1";
return 0;
}然而看看我们可爱贼短的标程
我打上面程序没有看标程因为。。。
知道自己看不懂
懒得看
千灯太ju(第3声)了
标程的方法同样是记录走过的路，不过明显比千灯的容易看懂 差不多
标程通过用team直接记录q队头队尾的x,y确定走过的路，而不是像千灯这样用明显二维记录，不过效果差不多
当然确定走过路的过程来说还是千灯的容易看懂
那么再贴一下标程：
//Coded by dst
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
struct Point{
int x,y,pre;
};
int n,m,sx,sy,tx,ty,px,py,head,tail,ans;
int map[1005][1005];//用0表示障碍，1表示无障碍，2表示终点
bool vis[1005][1005],got,second;
Point team[1000005];
inline void push(int x,int y){
if(map[x][y]&&!vis[x][y]&&!got){
vis[x][y]=1;
team[++tail].x=x,team[tail].y=y,team[tail].pre=head;
if(map[x][y]==2)
got=1;
}
}
void bfs(int sx,int sy){
got=0;
int x,y;
head=0,tail=0;
push(sx,sy);
do{
head++;
x=team[head].x,y=team[head].y;
push(x-1,y);
push(x,y+1);
push(x+1,y);
push(x,y-1);
}while(head<tail&&!got);
if(!got){
printf("-1\n");
exit(0);
}
}
int main(){
freopen("rescue.in","r",stdin);
freopen("rescue.out","w",stdout);
scanf("%d%d%d%d%d%d%d%d",&n,&m,&sx,&sy,&tx,&ty,&px,&py);
int i,j,t;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&t),map[i][j]=!t;
map[px][py]=2;
bfs(sx,sy);
for(t=tail;t;t=team[t].pre)
map[team[t].x][team[t].y]=2;
memset(vis,0,sizeof(vis));
memset(team,0,sizeof(team));
bfs(tx,ty);
for(t=team[tail].pre;t;t=team[t].pre)
ans++;
printf("%d\n",ans);
return 0;
}蒟蒻的注解，看看就好了！记得点赞---，虽然我也不知道有什么用