问题 3581 --千里眼与顺风耳

3581: 千里眼与顺风耳

时间限制: 1 Sec  内存限制: 256 MB
提交: 13  解决: 7
[提交][状态][讨论版][命题人:]

题目描述

千里眼和顺风耳是好朋友，现在顺风耳被困在一个迷宫不能行动，需要千里眼去解救。这个迷宫可以看成是一个由O和X的格点组成，O表示空地，X表示墙。墙不能通过也能阻挡千里眼的视线。现在千里眼从一个位置出发，去解救顺风耳。他只能向上、下、左、右移动。每次移动花费1秒。但千里眼如果能够通过一条直线看到顺风耳，他就可以使用法术，瞬间移动到顺风耳身边并解救。这条直线可以是向上、下、左、右的直线，也可是左上、右上、左下、右下的直线。千里眼希望你能帮他确定最短需要多长时间才能解救顺风耳。

输入

第一行两个整数N,M，表示迷宫的规模

接下来是N*M的迷宫，O表示空地，X表示墙

最后是多对数据，分别表示顺风耳和千里眼的坐标。（数据保证他们的坐标位置不可能是墙），每对占一行，0为结束标志。

输出

根据每对数据，计算千里眼解救顺风耳的最短时间。每行一对。如果不能解救，输出"FAILED"。

样例输入

3 4
OXXO
XXOO
XOOO
3 2 2 4
3 3 1 1
0 0 0 0

样例输出

1
FAILED

提示


数据范围



1<=N,M<=1000

来源

广搜bfs 

[提交][状态]