#D1018. 海盗队长信奥怪猫侠2
海盗队长信奥怪猫侠2
题目背景
2024年1月19日广附紫兰信奥队的集训教室突然来了一只漂亮的猫咪,不知何故这只猫咪的一只眼睛受到了非常严重的伤害。信奥队的同学们都非常担心这只可怜的猫咪,有的同学从家里拿了猫粮给它吃,我们善良美丽的吴老师专门带着这只可怜的流浪猫咪去宠物医院帮它治疗眼睛。猫咪也很乖,我们在上课的时候,它就乖乖的呆在电脑桌下面,慢慢的这只独眼猫咪跟着D老师也学会了神奇的信奥算法,并在信奥界所向披靡,成为我们紫兰信奥队的海盗队长信奥怪猫侠。从此信奥的江湖就有了猫哥的传说......
题目描述
某天校园里出现了一只老鼠,我们需要帮助这只独眼海盗队长信奥怪猫侠去抓住这只老鼠,现给定一张格的地图表示校园,地图由'#','.','*' 组成,'#'表示围墙,'*'表示我们信奥队的一位同学所在位置,'.'表示独眼海盗队长信奥怪侠猫无法逾越的障碍物。信奥队员为了能帮助猫咪需要先清除这些障碍物,但是每位同学目前信奥魔力值还不够,同学们清理障碍物的时候就像大家做信奥题一样暂时还不会拐弯,也就是他们只能清理他所在格子的上下左右四个直线方向的障碍物,而且直到遇到墙壁就停止。现在告诉你猫的位置(catx,caty)和老鼠的位置(mousex,mousey),猫只能沿着上下左右是个方向走,求猫能否抓到老鼠,如果能就输出猫的最小的方案步数,否则输出"No"。
输入格式
第一行输入两个数字n,m;
接下来输入n行m列的地图
最后一行输出四个数,分别表示catx,caty,mousex,mousey;
Output
猫抓到老鼠的最小步数或者"No"
样例
6 6
......
#.*...
......
..#...
.#...*
......
1 3 6 6
9
样例说明
样例中同学们清理完障碍物后用'o'表示通路,红色路线就是猫捉老鼠的路线。
..o..o
#o*ooo
..o..o
..#..o
.#ooo*
.....o
Limitation