蚱蜢
测试数据来自 system/1586
背景
安徽省芜湖市集训队第二次选拔
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