解题思路

1. 问题分析

• 场景建模：将城镇建模为一个$P×Q$的网格，每个网格点有高度值$Z_i,j$。
• 移动规则：技术员每次只能向相邻的四个方向（北、南、西、东）移动一步，且高度变化限制为：
  • 向上最多爬升$1$米$（Z_{i+1},j ≤ Z_i,j + 1）$
  • 向下最多下降$3$米$（Z_{i+1},j ≥ Z_i,j - 3）$
• 可见性条件：在移动的每一步结束时，至少有一个$BTS$（起点或终点）必须可见。可见性定义为两点之间（技术员当前位置和$BTS$位置）的连线不穿过任何固体立方体（即不遮挡视线）。

2. 关键挑战

• 路径搜索：需要在满足高度变化限制和可见性约束的条件下，找到从起点到终点的最短路径。
• 可见性检查：需要高效判断两点之间是否存在直接视线，即连线是否被地形遮挡。

3. 算法选择

• 广度优先搜索（BFS）：适用于无权图的最短路径问题，可以逐层扩展搜索空间。
  • 状态表示：每个状态包括当前位置$（i,j）$和当前步数。

代码实现

#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#define y1 ss
#define y2 sss
using namespace std;

struct node {
	int x, y, sum;
};

const double eps = 1e-8;
int a[205][205], n, m;

bool check(int x1, int y1, int x2, int y2) {
	bool flag = 1;
	double delta, deltah, now, nowh; 
	
	if(x1 == x2) goto checky;
	if(x2 < x1) swap(x1, x2), swap(y1, y2);
	delta = y2 - y1; delta /= x2 - x1;  
	deltah = a[x2][y2] - a[x1][y1]; deltah /= x2 - x1;  // Calculate height change
	now = y1 + 0.5 + 0.5 * delta;  // Initial intersection position
	nowh = a[x1][y1] + 0.5 + 0.5 * deltah;  
	for(int i = x1; i < x2; i++) {
		int nowgrid = floor(now), nowh1, nowh2;
		if(fabs(now - nowgrid) < eps) {
			nowh1 = a[i][(int)floor(now - 0.5 * fabs(delta)/delta)];
			nowh2 = a[i+1][(int)floor(now + 0.5 * fabs(delta)/delta)];
		} else {
			nowh1 = a[i][nowgrid];
			nowh2 = a[i+1][nowgrid];
		}
		if(nowh1 > nowh || nowh2 > nowh) {
			flag = 0;
			break;
		}
		now += delta; nowh += deltah;  
	}
	if(!flag) return false;
	
	checky:
	if(y1 == y2) goto out;
	if(y2 < y1) swap(y1, y2), swap(x1, x2);
	delta = x2 - x1; delta /= y2 - y1;
	deltah = a[x2][y2] - a[x1][y1]; deltah /= y2 - y1;
	now = x1 + 0.5 + 0.5 * delta;
	nowh = a[x1][y1] + 0.5 + 0.5 * deltah;
	
	for(int i = y1; i < y2; i++) {
		int nowgrid = floor(now), nowh1, nowh2;
		if(fabs(now - nowgrid) < eps) {
			nowh1 = a[(int)floor(now - 0.5 * fabs(delta)/delta)][i];
			nowh2 = a[(int)floor(now + 0.5 * fabs(delta)/delta)][i+1];
		} else {
			nowh1 = a[nowgrid][i];
			nowh2 = a[nowgrid][i+1];
		}
		if(nowh1 > nowh || nowh2 > nowh) {
			flag = 0;
			break;
		}
		now += delta; nowh += deltah;
	}
	
	out:
	return flag;
}

int x1, y1, x2, y2;
int can[205][205], vis[205][205];

bool CanSee(node tmp) {
	if(can[tmp.x][tmp.y] != -1) return can[tmp.x][tmp.y];
	if(check(tmp.x, tmp.y, x1, y1) || check(tmp.x, tmp.y, x2, y2)) {
		can[tmp.x][tmp.y] = 1;
	} else {
		can[tmp.x][tmp.y] = 0;
	}
	return can[tmp.x][tmp.y];
}

const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
queue<node> q;

bool ok(node u, node v) {
	if(a[u.x][u.y] > a[v.x][v.y]) {
		return (a[u.x][u.y] - a[v.x][v.y]) <= 3;
	} else {
		return (a[v.x][v.y] - a[u.x][u.y]) <= 1;
	}
}

void initializeArrays() {
	for(int i = 0; i < 205; i++) {
		for(int j = 0; j < 205; j++) {
			can[i][j] = -1;
		}
	}
	
	for(int i = 0; i < 205; i++) {
		for(int j = 0; j < 205; j++) {
			vis[i][j] = 0;
		}
	}
}

int bfs() {
	if(x1 == x2 && y1 == y2) return 0;
	
	initializeArrays();  
	
	node tmp;
	tmp.x = x1; tmp.y = y1; tmp.sum = 0;
	while(!q.empty()) q.pop();
	q.push(tmp);
	vis[x1][y1] = 1;
	
	while(!q.empty()) {
		node now = q.front();
		q.pop();
		
		for(int i = 0; i < 4; i++) {
			tmp.x = now.x + dx[i];
			tmp.y = now.y + dy[i];
			tmp.sum = now.sum + 1;
			
			if(tmp.x >= 1 && tmp.x <= n && tmp.y >= 1 && tmp.y <= m && 
				ok(now, tmp) && !vis[tmp.x][tmp.y] && CanSee(tmp)) {
				if(tmp.x == x2 && tmp.y == y2) return tmp.sum;
				q.push(tmp);
				vis[tmp.x][tmp.y] = 1;
			}
		}
	}
	return -1;
}

int main() {
	int T;
	scanf("%d", &T);
	while(T--) {
		scanf("%d%d", &n, &m);
		
		for(int i = 0; i < 205; i++) {
			for(int j = 0; j < 205; j++) {
				a[i][j] = 0;
			}
		}
		
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= m; j++) {
				scanf("%d", &a[i][j]);
			}
		}
		
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		int ans = bfs();
		
		if(ans == -1) {
			printf("Mission impossible!\n");
		} else {
			printf("The shortest path is %d steps long.\n", ans);
		}
	}
	return 0;
}