#P3848. [TJOI2007] 跳棋

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

[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

提示

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