单挑女飞贼

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m;
int sx, sy, ex, ey;//分别是起点的x坐标y坐标，终点的x坐标y坐标
int dis[205][205];//存放从sx, sy到其它点的距离，二维数组下标就是点坐标，若到不了距离为-1
bool vis[205][205];//存放该点是否访问过，避免重复访问
string maze[205]//地图
int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1}, dy[8] = {0, 0, -1, 1, -1, 1, 1, -1};//八个方向，从左往右分别是上 下 左 右 左上 右上 右下 左下，拿相同下标的dx dy搭配可以让当前坐标往特
																																						//定方向移动
void bfs(){
	for(int i=0; i<n; i++)//这一步是初始化，将一开始到所有点的距离都设为-1，访问标识都设为false
		for(int j=0; j<m; j++)
			dis[i][j] = -1, vis[i][j] = false;
	queue<pair<int, int>> q;//bfs的队列
	q.push({sx, sy});//将起点加入队列
	dis[sx][sy] = 0;//起点到起点的距离为0
	vis[sx][sy] = true;//起点访问过，就标为true
	while(!q.empty()){
		pair<int, int> t = q.front(); q.pop();//从队列取点
		for(int i=0; i<8; i++){
			//这个循环的作用是遍历八个方向，看能否打到女飞贼

			//这里就能看出dx, dy是怎么起作用的
			int nx = t.first + dx[i];
			int ny = t.second + dy[i];
			while(1){
				if(nx == ex && ny == ey){
					//这里说明打到了
					cout << dis[t.first][t.second] << endl;
					return;
				}
				if(nx < 0 || nx >= n || ny < 0 || ny >= m || maze[nx][ny] == ‘X‘) break;//这里说明受阻了，飞镖停下来

				//继续往该方向深入
				nx += dx[i];
				ny += dy[i];
			}
		}
		//做完上面的扫描后，能到这一步说明该结点没打到，继续处理该结点附近的结点，入队列
		for(int i=0; i<4; i++){
			//四个方向移动
			int nx = t.first + dx[i];
			int ny = t.second + dy[i];
			if(nx >= 0 && nx < n && ny >= 0 && ny < m && maze[nx][ny] != ‘X‘ && !vis[nx][ny]){
				//将四个方向的格子加入队列，距离为当前起点到当前结点的距离+1
				q.push({nx, ny});
				dis[nx][ny] = dis[t.first][t.second] + 1;
				vis[nx][ny] = true;
			}
		}
	}
	//全部走完了还没有return说明打不到
	cout << "Impossible!" << endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=0; i<n; i++)//都是输入，不用多讲
		cin >> maze[i];
	while(cin >> ex >> ey >> sx >> sy){
		if( sx == 0 && sy == 0 && ex == 0 && ey == 0 ) break;
		sx--; sy--; ex--; ey--;
		bfs();//bfs的作用是，得到sx, sy为起点，到其它每一个点的最短距离
	}
	return 0;
}