Description

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

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

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

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

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

Samples 輸入資料 1 3 4 OXXO XXOO XOOO 3 2 2 4 3 3 1 1 0 0 0 0 輸出資料 1 1 FAILED Limitation 数据范围

1<=N,M<=1000

1s, 1024KiB for each test case.

代码：

#include <bits/stdc++.h>
using namespace std;
int n,m, bgx, bgy, edx,edy;
struct Node{
	int x;
	int y;
	int stp;
};
bool f[305][305];
char g[305][305];
int dx[10]={0,0,1,-1}, dy[10]={1,-1,0,0};

bool cal(int x, int y){
	if (x==edx&&y<edy){
		bool flg1=false;
		for (int i=y;i<=edy;i++){
			if (g[x][i]=='X') {
				flg1=true;
				break;
			}
		}
		if (!flg1) return true;
	}
	else if (x==edx&&y>edy) {
		bool flg2=false;
		for (int i=edy;i<=y;i++){
			if (g[x][i]=='X') {
				flg2=true;
				break;
			}
		}
		if (!flg2) return true;
	}
	if (y==edy&&x<edx){
		bool flg3=false;
		for (int i=x;i<=edx;i++){
			if (g[i][y]=='X') {
				flg3=1;
				break;
			}
		}
		if (!flg3) return true;
	}
	else if (y==edy&&x>edx){
		bool flg4=false;
		for (int i=edx;i<=x;i++){
			if (g[i][y]=='X') {
				flg4=1;
				break;
			}
		}
		if (!flg4) return true;
	}
	if (y>=edy&&x>=edx&&y-edy==x-edx){
		bool flg5=false;
		int xx=edx, yy=edy;
		while (xx<=x&&yy<=y){
			if (g[xx][yy]=='X'){
				flg5=false;
				break;
			}
			xx+=1;
			yy+=1;
		}
		if (!flg5) return true;
	}
	else if (y<edy&&x<edx&&edy-y==edx-x){
		bool flg6=false;
		int xx=edx, yy=edy;
		while (xx>=x&&yy>=y){
			if (g[xx][yy]=='X'){
				flg6=false;
				break;
			}
			xx-=1;
			yy-=1;
		}
		if (!flg6) return true;
	}
	if (y<=edy&&x>=edx&&edy-y==x-edx){
		bool flg7=false;
		int xx=x, yy=y;
		while (xx>=x&&y<=edy){
			if (g[xx][yy]=='X'){
				flg7=false;
				break;
			}
			xx-=1;
			yy+=1;
		}
		if (!flg7) return true;
	}
	else if (y>edy&&x<edx&&edy-y==x-edx){
		bool flg8=false;
		int xx=x, yy=y;
		while (xx>=x&&y<=edy){
			if (g[xx][yy]=='X'){
				flg8=false;
				break;
			}
			xx+=1;
			yy-=1;
		}
		if (!flg8) return true;
	}
	return false;
}
signed main(){
	scanf("%d%d", &n, &m);
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			cin>>g[i][j];
		}
		
	}
	
	while (true){
		queue<Node>q;
		bool flg=true;
		cin>>bgx>>bgy>>edx>>edy;
		if (bgx==0&&bgy==0&&edx==0&&edy==0){
			break;
		}
		q.push({bgx, bgy, 0});
		memset(f, 0, sizeof(f));
		f[bgx][bgy]=1;
		while (q.size()){
			Node t=q.front();
			q.pop();
			int x=t.x; 
			int y=t.y;
			int stp=t.stp;
			if (x==edx&&y==edy){
				cout << stp << endl;
				flg=false;
				break;
			}
			if (cal(x, y)){
				cout << stp+1<<endl;
				flg=false;
				break;
			} 
			
			for (int i=0;i<4;i++){
				int xx=x+dx[i], yy=y+dy[i];
				if (xx>=1&&xx<=n&&yy>=1&&yy<=m&&g[xx][yy]=='O'&&!f[xx][yy]){
					q.push({xx, yy, stp+1});
					f[xx][yy] =1;
				}
			}
		}
		if (flg){
			cout << "FAILED"<<endl;
		}
	}
	return 0;
}