本文主要是介绍死亡洞穴(cave)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目背景
在 caima 的 RPG 游戏中，控制着两个人 VV 和 JJ。 这次 VV 和 JJ 掉入了一个死亡洞穴，洞穴是一个 N*M 的矩阵。之所以称之 为死亡洞穴，是因为在这个矩阵中有一些死亡十字。(如下图中的+)
…
.+++.
.+.+.
V+.J+
由于 VV 和 JJ 被分撒在了两地，而 JJ 还受了重伤，你需要让 VV 赶到 JJ 所 在的地方。为了尽量少的受死亡十字的影响，VV 要尽量远离这些死亡十字。 我们定义洞穴中两个格子(x,y)和(x’,y’)之间的距离为： 也就是说，我们要使得 VV 再去找 JJ 的路上，离任意死亡十字的距离都尽 可能的远。VV 每次可以往一个格子的上下左右四个方向走一格。 现在你需要写个程序，来计算最好情况下离死亡十字最近的距离。
题目描述
输入输出格式
输入格式：
第一行两个整数 N 和 M，表示矩阵规模。 接下来 N M 列，描述这个洞穴的情况。其中 V 表示 VV 所在的位置； J 表示 JJ 所在的位置； . 表示空地；
表示死亡十字。
输出格式：
一行一个数字，表示 VV 在去找 JJ 的路上，最好情况下离死亡十字最近的距 离。
输入输出样例
输入样例
4 4
+…
…
…
V…J
输出样例
3
说明
对于 30% 的数据 N,M≤50。 对于 100% 的数据 N,M≤500。
看完题目感觉无从下手，在教练的一番指点后才发现这居然是一道二分答案+bfs。
思路：二分最近的十字架距离，再bfs判断是否可以。本题考点主要在于想出二分和如何bfs。
代码：
const z:array[1..4,1..2]of -1..1=((1,0),(-1,0),(0,1),(0,-1));
var i,j,k:longint;m,n,h,t:longint;ch:char;fx,fy,lx,ly:longint;l,r,mid,ans:longint;a:array[0..501,0..501]of longint;b,p:array[0..501,0..501]of boolean;x,y,u:array[0..1000000]of longint;
function bfs(min:longint):boolean;//bfs也就是二分中的check
var i:longint;
beginp:=b;h:=1;t:=1;x[1]:=fx;y[1]:=fy;p[x[1],y[1]]:=false;if (fx=lx) and (fy=ly) then exit(true);//可以到终点repeatfor i:=1 to 4 doif p[x[t]+z[i,1],y[t]+z[i,2]] and (a[x[t]+z[i,1],y[t]+z[i,2]]>=min) then//满足距离条件begininc(h);x[h]:=x[t]+z[i,1];y[h]:=y[t]+z[i,2];p[x[h],y[h]]:=false;if (x[h]=lx) and (y[h]=ly) then exit(true);end;inc(t);until t>h;exit(false);//不可以到终点
end;
beginread(m,n);readln;h:=0;t:=1;for i:=1 to m dobeginfor j:=1 to n dobeginread(ch);if ch='V' then begin fx:=i; fy:=j; end;if ch='J' then begin lx:=i; ly:=j; end;if ch='+' then begin inc(h); x[h]:=i; y[h]:=j; b[i,j]:=false; a[i,j]:=0; u[h]:=0; endelse b[i,j]:=true;end;readln;end;p:=b;//给每个位置标记上距离，利用bfs必定先找到最优解repeatfor i:=1 to 4 doif p[x[t]+z[i,1],y[t]+z[i,2]] thenbeginp[x[t]+z[i,1],y[t]+z[i,2]]:=false;inc(h);x[h]:=x[t]+z[i,1];y[h]:=y[t]+z[i,2];u[h]:=u[t]+1;a[x[h],y[h]]:=u[h];end;inc(t);until t>h;l:=1;r:=a[fx,fy];if a[lx,ly]<r then r:=a[lx,ly];//最大必定不比起点和终点的小的值大while l<=r do//二分beginmid:=(l+r) div 2;if bfs(mid) then begin l:=mid+1; ans:=mid; {记录答案}end else r:=mid-1;end;write(ans);//输出
end.
如果大家不明白
给每个位置标记上距离，利用bfs必定先找到最优解
则先做一下这题：
题目描述
给出一个N*M的01矩阵，求每个点离它最近的数字1的点的距离是多少。距离是曼哈顿距离。(平面上，坐标（x1, y1）的点P1与坐标（x2, y2）的点P2的曼哈顿距离为：|x1 - x2| + |y1 - y2|.)
输入格式：
第一行两个数N,M
后面N行，每行M个字符，为0或1
输出格式：
共输出N行，每行M个数，用空格分开。
输入输出样例
输入样例
3 4
0001
0011
0110
输出样例
3 2 1 0
2 1 0 0
1 0 0 1
说明
50%的数据,N,M<=100
100%的数据,N,M<=1000
这题便是上题目的一个简化题，题目更清晰。
代码：
const z:array[1..4,1..2]of -1..1=((1,0),(-1,0),(0,1),(0,-1));
var i,j,k:longint;m,n:longint;a:array[0..1001,0..1001]of longint;b:array[0..1001,0..1001]of boolean;ch:char;h,t:longint;x,y,u:array[0..1000000]of longint;
beginh:=0;t:=1;readln(m,n);for i:=1 to m dofor j:=1 to n dob[i,j]:=true;for i:=1 to m dobeginfor j:=1 to n dobeginread(ch);if ch='1' then//如果为1则入队列beginb[i,j]:=false;a[i,j]:=0;inc(h);u[h]:=0;x[h]:=i;y[h]:=j;end;end;readln;end;repeat//根据bfs的性质可得第一个找到的便是那一个0距离最近的一个1的距离。for i:=1 to 4 doif b[x[t]+z[i,1],y[t]+z[i,2]] thenbegininc(h);x[h]:=x[t]+z[i,1];y[h]:=y[t]+z[i,2];u[h]:=u[t]+1;b[x[h],y[h]]:=false;a[x[h],y[h]]:=u[h];end;inc(t);until t>h;for i:=1 to m do//输出便可beginfor j:=1 to n do write(a[i,j],' ');writeln;end;
end.
这篇关于死亡洞穴(cave)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
