/ Vijos / 题库 /

蚱蜢

蚱蜢

背景

安徽省芜湖市集训队第二次选拔

COCI 2008/2009 Contest #1 - skakavac

Description:Unknown(Chinese Simplified)
Data:Official
Program:Official

描述

一只蚱蜢在花园里。这块土地包含n*n的花朵按n行n列排列。我们知道每朵花的花瓣数。这只蚱蜢的初始位置在r行c列。它的目标是在遵守以下规则的同时访问的花越多越好。

●它只可以跳到相邻的行或列,如果它跳到了相邻的行,它必须至少跳两列;如果它跳到了相邻的列,它必须至少跳两行。换句话说就是,它可以从花(r1,c1)跳到花(r2,c2),如果:
(|r1-r2|==1 && |c1-c2|>1) || (|c1-c2|==1 && |r1-r2|>1)
●下一朵花的花瓣数必须严格大于当前花的花瓣数。

写一个程序,计算出蚱蜢可以访问的花的最多的数目。

格式

输入格式

第一行包括一个整数n(1<=n<=1500),表示土地的大小。

第二行包括两个整数r(1<=r<=n)和c(1<=c<=n),表示蚱蜢的初始位置。

下面n行,每行包括n个正整数,每个小于1,000,000,表示花的花瓣数。

输出格式

输出仅一行,为蚱蜢可以访问的最多的花的数目。

样例1

样例输入1

#1:
4
1 1
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7

#2:
5 
3 3 
20 16 25 17 12 
11 13 13 30 17 
15 29 10 26 11 
27 19 14 24 22 
23 21 28 18 13 

样例输出1

#1:
4

#2:
21

限制

每个点4 seconds.

提示

50%的数据中,n最大为100。

80%的数据中,n最大为1000。

最大数据14MB。

来源

安徽省芜湖市集训队第二次选拔

COCI 2008/2009 Contest #1 - skakavac

Description:Unknown(Chinese Simplified)
Data:Official
Program:Official

信息

ID
1586
难度
8
分类
动态规划 | 数据结构 点击显示
标签
(无)
递交数
310
已通过
44
通过率
14%
上传者

相关

在下列训练计划中:

RP++分类题库