#P3848. [TJOI2007] 跳棋
[TJOI2007] 跳棋
题目背景
在一个n×n的棋盘上,布满了0和1,如图(a)所示(n=7),为叙述方便,将0用字母表示,如图(b)。
题目描述
跳棋规则:
(1)从某个0格出发,可以向上,下,左,右4个方向连续越过若干个(至少1个)
1格而跳入下一个0格。如图(b)中从A出发,可跳到B,或者到E,但不能直接到K。在跳到B之后还可以继续跳到F;在跳到E之后可继续跳到F或K。直到不能再跳为止。
(2)每个0格只能到达一次,给出的起始点不能再到达,也不能越过。
跳过的距离为跳过1格个数加1,如从A到B,跳过距离为3,从B到F,跳过距离为2。
问 题: 当棋盘和起始点给出之后,问最远能跳的距离是多少?
如上图(b)中,从A出发,可跳过的路线不止一条,其中一条为:
A - B - F - L - K - E (可能不唯一)
3 2 3 3 3
它的距离为14。
输入格式
第一行三个整数 n(1≤n≤100),x,y(起点坐标,上图(b)中A处坐标为1,3)
接下来n行,每行n个数(0或1),数与数之间用一个空格分隔。
输出格式
一个整数,即最大可跳距离(若不能跳,输出0)。
4 3 2
1 0 1 0
1 1 1 1
0 0 1 0
1 1 0 1
6
提示
:新增加一组 Hack 数据。