方格取数
-
方格取数
（一）问题描述
设有
N
＊
N
的方格图
（
N
≤
8
）
，
我们将其中的某些
方格中填入正整数，
而其他的方格中则
放入数字
0
。如下图所示（见样例）
：
向右
A
1
2
3
4
5
向
下
6
7
8
1
0
0
0
0
0
0
2
0
0
0
3
0
0
0
4
0
0
0
0
0
5
0
0
7
0
0
0
0
6
0
6
0
0
4
0
0
0
7
0
0
0
0
0
0
0
0
8
0
0
0
0
0
0
0
0
B
0
13
0
14
0
0
21
0
0
14
0
0
0
0
15
0
某人从图的左上角的
A
点出发，可以向下行走，也可以向右走，直到到达右下角的
B
点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为
数字
0
）
。
此人从
A
点到
B
点共走两次，试找出
2
条这样的路径
，使得取得的数之和为最大。
输
入
输入的第一行为一个整数
N<
/p>
（表示
N
＊
N<
/p>
的方格图）
，接下来的每行有三个整数，前两个
< br>表示位置，第三个数为该位置上所放的数。一行单独的
0
表示输入结束。
输
出
只需输出一个整数，表示
2<
/p>
条路径上取得的最大的和。
样
例
输入
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
输出
67
（二）
问题分析
< br>本题是从
1997
年国际信息学奥林匹克的障碍物探测器
一题简化而来，如果人只能从
A
点到
B
点走一次，
则可以用动态规划算法求出从
A
点到
B
点的最优路径。
具体的算法描述如
下：从
A
点开始，向右和向下递推，依次求出从
A
点出发到达当前位置
（
i
，
j
）所
能取得的
最大的数之和，存放在
sum
数组中，原始数据经过转换后用二维数组
data
存储，为方便
处
理，对数组
sum
和
data
加进零行与零列，并置它们的零行与零列元素为
0
。易知
data[i
，
j]
当
i=0
或
j=0
sum[i
，
j]=
max
（
sum[i-1
，
j]
，
sum[i
，
j-1]
）
+
data[i
，
j]
当
i>0,
且
j>0
求出
sum
数组以后，通过倒推即可求得最优路径，具体算法如下：
置
sum
数组零行与零列元素为
0
for i:=1 to n do
for j:=1 to n
do
if sum[i-1,j]>sum[i,j-1]
then
sum[i,j]:=sum[i-1,j]+data[i,j]
else sum[i,j]:=sum[i,j-1]+data[i,j];
i:=n; j:=n;
while (i>1) or (j>1)
do
if (i>1) and
(sum[i,j]=sum[i-1,j]+data[i,j])
then begin data[i,j]:=-1; i:=i-1 end
else begin data[i,j]:=-1; j:=j-1 end;
data[1,1]:=-1;
凡是被标上
-1
的格子即构成了从
A
点到
B
点的一条最优路径。
那么是否可以按最优路径连续走两次而取得最大数和呢
?
这是一种很自然的想法
,
并且
对样例而言也是正确的
,
具体算法如下：
1
、
求出数组
sum
，
2
、
s1:=sum[n,n]
，
3
、
4
、
求出最优路径，
将最优路径上的格子
中的值置为
0
，
5
、
将数组
sum
的所有元素置为
0
，
6
、
第二次
求出数组
sum
，
7
、
输出<
/p>
s1+sum[n,n]
。
虽然这一算法保证了连续的两次走法都是最优的，但却
不能保证总体最优，相应的反
例也不难给出，请看下图：
图二按最优路径走一次后，余下的两个数
2
和
3
就不可能同时取倒
了，而按图三中的
非最优路径走一次后却能取得全部的数，
这是
因为两次走法之间的协作是十分重要的，
而图
2
中的走法并不能考虑全局，因此这一算法只能算是“贪心算法”
。虽然在一些情
况下，贪
心算法也能够产生最优解，但总的来说“贪心算法”是一种有明显缺陷的算法。
既然简单的动态规划行不通，
那么看
看穷举行不行呢？因为问题的规模比较小，
启发我
们从穷举的角
度出发去思考，
首先让我们来看看
N=8
时，
从左上角
A
到达右下角
B
的走法共
有多少种呢？显然从
A
点到
B
点共需走
14
步，
其中向右走
7<
/p>
步，
向下走
7
步
，
共有
C
14
=3432
种不同的路径，
走两次的路径组合总数为
C
3432
=3432
＊
3431/2=5887596
，
从时
间上看是完全
可以承受的，
但是如果简单穷举而不加优化的话，
对极限数据还是会超时的，
优化的最基本
的方法是以空间换时间，
具体到本题就是预先将每一条路径以及路径上的数字之和
（称之为
2
7
路径
的权
weight
）求出并记录下来，然后用双重循环穷举任意
两条不同路径之组合即可。
考虑到记录所有的路径需要大量的存储空间，
我们可以将所有的格子逐行进行编号，
这样原
2
来用二维坐标表示的格子就变成用一个
1
到<
/p>
n
之间的自然数来表示，格子（
i,j<
/p>
）对应的编
号为（
i-1
）
*n+j
。一条路径及其权使用以下的数据结构表示
：
const maxn=8;
type arraytype=array[1..2*maxn-2] of
byte;
recordtype=record
path:arraytype;
weight:longint
end;
数组
path
依次记录一条路径上除左上和右
下的全部格子的编号。
将所有的路径以及路径的权求出并记录
下来的算法可用一个递归的过程实现，
其中
i,j
表示当前位置的行与列，
step
表示步数，
sum
记录当前路径上到当前位置为止的数之和，
当
前路径记录在数组
position
中（不记录起始格）
，主程序通过调用
try(1,1,0
,data[1,1])
求得所有路径。
procedure try(i,j,step,sum:longint);
begin
if (i=n) and
(j=n)
then begin
total:=total+1;
a[total].path:=position;
a[total].weight:=sum;
end
else begin
if i+1<=n then
begin
position[step]:=i*n+j;
try(i+1,j,step+1,sum+data[i+1,j])
end;
if j+1<=n then
begin
position[step]:=(i-1)*n+j+1;
try(i,j+1,step+1,sum+data[i,j+1])
end
end
end;
在穷举了二条不同的路径后，
只要将二条路径的权相加再减去二条路径
中重叠格子中的
数即为从这二条路径连走两次后取得的数之和，具体算法如下：
for i:=1 to n do
{
将二维数组转化为一维数组
}
for j:=1 to n do d1[(i-1)*n+j]:=data[i,j];
max:=0;
for i:=1
to total-1 do
for j:=i+1 to
total do
begin
current:=a[i].weight+a[j].weight;
for k:=1 to 2*n-3 do
{
判断重叠格子，但不包括起点的终点
}
begin
if a[i].path[k]=a[j].path[k]{
第
k
步到达同一方格
}
then current:=current-d1[a[i].path[k]]
end;
if current>max then
max:=current
end;