#P3848. [TJOI2007] 跳棋

    ID: 2769 Type: RemoteJudge 1000ms 128MiB Tried: 0 Accepted: 0 Difficulty: 5 Uploaded By: Tags>搜索2007各省省选递归深度优先搜索,DFS天津

[TJOI2007] 跳棋

题目背景

本题可能为错题,目前数据只是随机生成的 n20n\leq 20 的情况,测试数据和题解仅供参考。

在一个 n×nn \times n 的棋盘上,布满了 0 和 1,如图(a)所示(n=7n=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=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 数据。