#P3848. [TJOI2007] 跳棋

    ID: 2764 远端评测题 1000ms 128MiB 尝试: 1 已通过: 1 难度: 5 上传者: 标签>搜索2007各省省选递归深度优先搜索,DFS天津

[TJOI2007] 跳棋

说明

跳棋规则:

(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=143+2+3+3+3=14

它的距离为 1414

输入格式

第一行三个整数 n(1n100)n(1 \le n \le 100)xxyy(起点坐标,上图(b)中 A 处坐标为 (1,3)(1,3))。

接下来 nn 行,每行 nn 个数(0 或 1),数与数之间用一个空格分隔。

输出格式

一个整数,即最大可跳距离(若不能跳,输出 0)。

4  3  2
1  0  1  0 
1  1  1  1
0  0  1  0
1  1  0  1
6

提示

upd 2022.7.27\text{upd 2022.7.27}:新增加一组 Hack 数据。