赵云在长坂坡为了救阿斗,曾经在曹军阵中七进七出,现在赵云陷入在曹操的兵阵之中,请你帮忙规划一下路线,让赵云能最快速度的到达阿斗所在的位置。
小兵给了赵云一个地图,地图中有2种字母,X表示是山地或者水塘,无法行走,F表示在i据点有个通道通往j据点,但是有个小兵在镇守。
他可以在小兵没反应过来之前快速通过他当前区域的第一个通道,但是他不选择第i个通道去走第i+1通过,他会惊动i个通道的士兵,所以他就需要击败第i个士兵才能去i+1个通道。
请问赵云最少需要击败几个士兵才可以到阿斗的边上!
第一行一个数字n,表示阿斗有可能在的n的地点,赵云一开始在1号地点;
接下来n行,每行n个字符,里面只包含X和F;
最后一行,一个数字a,表示阿斗在的地点;
一个数字k,表示赵云至少需要击败k个士兵,才能找到阿斗;
如果救不了阿斗,就输出'Fail'
4 XXFF XXXF FFXX XXFF 2
1
8 XXFFXXFF XXFFXXFF XXXXXXFF XXXXXXFF XXXXXXFF FFXXXXXX FFXXXXXX FFXXXXXX 8
1
样例说明:
样例1:
赵云一开始在1号地点,可以在守护三号通道的士兵反应过来之前去往3号地点,然后赵云击败守护一号通道的士兵,来到2号通道前,在2号通道守卫反应过来之前直接去4号地点,就可以救下阿斗了!
样例2:
赵云一开始在1号地点,直接通过3号通道道道3号地点,然后击败7号守卫,直接通过8号通道,来到8号地点,救下阿斗!
图示如下,只需要击败一个士兵即可!
数据范围:
对于 30\% 的数据:1 \le N \le 10;
对于 60\% 的数据:1 \le N \le 100;
对于 100\% 的数据:1 \le N \le 500。