在一个nxn的棋盘上布满了0和1,如图(a)所示(n=7)。为叙述方便,将0用字母表示,如图(b)所示。
跳棋规则如下:
(i)从某个0格出发,可以向上、下、左、右4个方向连续越过若干个(至少1个)1格后跳人下一个0格。如图(b)所示,从A出发,可跳到 B,或者跳到E,但不能直接跳到K。在跳到B之后还可以继续跳到F,在跳到E之后可继续跳到
F或K,直到不能再跳为止。
(ii)每个0格只能到达一次,给出的起始点不能再次到达,也不能越过。跳过的距离为跳过1格的个数加1,如从A到B,跳过距离为3,从B到F,跳过距离为 2。
问题:当给出棋盘和起始点之后,最远能跳的距离是多少?
如图(b)所示,从A出发,可跳的路线不止一条,其中一条为:
A--B--F--L--K--E(可能不唯一)
2 3 3 3 3
它的跳过距离为 14。
输人格式:
第1行3个整数n(1≤n≤100)、x、y(x,y是起始点坐标,图(b)中A处坐标为1,3)。接下来n行,每行n个数(0或1),数与数之间用一个空格分隔。
输出格式:
一个整数,即最大可跳距离(若不能跳,则输出0)。输入样例:
4 3 2
1010
1 111
0010
1101
输出样例:
6
①处应填()
0
max(ans,step)
1
step
②处应填()。
vis[tx][ty] == 1
vis[tx][ty] == 0
a[tx][ty]== 1
a[tx][ty] == 0
③处应填()
step+s
step+1
step
step-1
④处应填()
vis[tx][ty]= 1
vis[tx][ty]= 0
altx][ty]= 1
a[tx][ty]= 0
⑤处应填()
a[x][y]= 1
a[x][y]= 0
vis[x][y]= 1
vis[x][y]= 0
发表评论