http://poj.org/problem?id=1399
http://acm.hit.edu.cn/hoj/problem/view?id=1037
题意：
在一个最多200*200的minecraft方块地图上（由很多1*1*1的方块搭起来的地图，最高5000），其中两块分别有高0.5米的激光塔，有一个高0.5米的机器人要从其中一个激光塔走到另一个。要求只能走相邻4个方向，每次不能爬上超过1格或跳下超过3格（咦，好像真的很像minecraft），要求每走到一个格子，机器人站在在这个格子的中心，能直接接收到至少一个激光塔照射（机器人的头顶与激光塔的顶部连成的直线没有被地形挡住）。
还有就是，地形有缝隙，例如：
1 9
9 1
这样的2*2的地图，在两个高度为1的地形上是可以互相接收到激光的，因为两个9之间有条缝。
题解：
宽搜走路，难点在于判断一格是否能走。
最关键的函数：判断两个格子A、B之间是否被挡。
可分为两部分判断：
1.以x轴为基准，x=Ax,x=Ax+1,x=Ax+2……x=Bx。针对每个x，计算得出浮点数Y（由激光在地平面上的斜率计算得到），可以通过floor（向下取整）得到整数y，得到激光经过(x,y) 和(x+1, y)两个格子之间的交界处，通过这两个格子的高度和激光当时的高度（由激光在竖直切面的斜率计算得到），判断是否被遮挡。
2.以y轴为基准，同上。
上面只说了没有通过缝隙的情况。若发现Y为整数，则是通过了缝隙，在x为轴的情况下，此时改为判断(x,floor(Y-0.5p))和(x+1,floor(Y+0.5p))，p为1或-1，与地平面斜率同号。以y为轴类似。
这个函数写对了其他就简单了。
-------------------------------------------------------------------
这题就难在判断光线可见，建议解题时画出平面图，写出代数公式，研究各种情况的通用判断方法。
程序过不了样例，就调试观察判断激光可见的过程，找到错误。
我写的时候出的错主要在x轴y轴分类讨论有问题、对缝隙情况判断有问题。
代码见下，我写得屁滚尿流，有很多地方有简化得更加清晰明了的余地，仅供参考
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define RD(x) scanf("%d",&x)
#define REP(i,n) for(i=0;i<n;i++)
const int MAXN=;
const int g[][]= {{,,,-},{-,,,}};
const double eps=1e-;
int n,m;
int a[MAXN][MAXN];
int p[][];
bool visited[MAXN][MAXN];
int seeChecked[MAXN][MAXN];
bool ok(int now[], int next[]) {
int y=next[], x=next[];
int h1=a[now[]][now[]];
int h2=a[next[]][next[]];
if(x< || y< || x>=n || y>=m)return false;
if(h2-h1> || h1-h2>)return false;
return true;
} bool canSee2Dot(int x1,int y1,int x2,int y2) {
bool re=true;
int k;
int p[][];
p[][]=x1;
p[][]=y1;
p[][]=x2;
p[][]=y2;
// printf("(%d,%d)->(%d,%d)\n",x1,y1,x2,y2);
REP(k,) {
int st0=p[][k],ed0=p[][k];
int st1=p[][k^], ed1= p[][k^];
if(st0==ed0)continue;
if(ed0<st0) {
swap(ed0,st0);
swap(ed1,st1);
}
// printf("k=%d,%d->%d\n",k,st0,ed0);
double kk=ed1-st1;
kk/=ed0-st0;
double hk=a[ed0][ed1] - a[st0][st1];
if(k==)hk=a[ed1][ed0]-a[st1][st0];
hk/=ed0-st0;
double now = st1 + 0.5 + 0.5*kk;
double nowh = a[st0][st1] + 0.5 + 0.5 * hk;
if(k==)nowh = a[st1][st0] + 0.5 + 0.5*hk;
// printf("%d,%d,%f,%f\n",st0,st1,hk,nowh);
for(int i=st0; i<ed0; i++) {
int theNow = floor(now);
int theX,theY;
double theH1,theH2;
if(fabs(now-round(now))>eps) {
if(k==) {
theX=i;
theY=theNow;
theH1=a[theX][theY];
theH2=a[theX+][theY];
} else {
theX=theNow;
theY=i;
theH1=a[theX][theY];
theH2=a[theX][theY+];
}
// printf("%d,%d,%f,%f,%f,(%f)\n",theX,theY,theH1,theH2,nowh,now); } else {
if(k==) {
theX=i;
theY=floor(now-0.5*fabs(kk)/kk);
theH1=a[theX][theY];
theH2=a[theX+][(int)floor(now+0.5*fabs(kk)/kk)];
} else {
theX=floor(now-0.5*fabs(kk)/kk);
theY=i;
theH1=a[theX][theY];
theH2=a[(int)floor(now+0.5*fabs(kk)/kk)][theY+];
}
// printf("%d,%d,%f,%f,%f,(%f)\n",theX,theY,theH1,theH2,nowh,now);
}
if(theH1>nowh || theH2>nowh) {
re=false;
break;
}
now+=kk;
nowh+=hk;
}
if(!re)break;
}
return re;
} bool canSee(int d[]) {
int x=d[], y=d[];
if(seeChecked[x][y]!=-)return seeChecked[x][y];
bool re=canSee2Dot(x,y,p[][],p[][]) || canSee2Dot(x,y,p[][],p[][]);
seeChecked[x][y]=re;
return re;
}
int farm() {
int b[MAXN*MAXN][];
int bl=,br=;
int i;
if(p[][]==p[][] && p[][]==p[][])return ;
memset(visited,,sizeof(visited));
memset(seeChecked,-,sizeof(seeChecked));
b[][]=p[][];
b[][]=p[][];
while(bl<br) {
int now[];
now[]=b[bl][];
now[]=b[bl][];
now[]=b[bl][];
// printf("now(%d,%d)\n", now[0],now[1]);
bl++;
REP(i,) {
int next[];
next[] = now[]+g[][i];
next[] = now[]+g[][i];
next[] = now[]+;
if(!visited[next[]][next[]] && ok(now,next) && canSee(next)) {
if(next[]==p[][] && next[]==p[][])return next[];
b[br][]=next[];
b[br][]=next[];
b[br][]=next[];
br++;
visited[next[]][next[]]=true;
}
}
}
return -;
} int main() {
int T,i,j;
int x;
RD(T);
while(T--) {
scanf("%d%d",&n,&m);
REP(i,n)REP(j,m)RD(a[i][j]);
scanf("%d%d%d%d",&p[][],&p[][], &p[][], &p[][]);
p[][]--;
p[][]--;
p[][]--;
p[][]--;
x = farm();
if(x!=-)printf("The shortest path is %d steps long.\n",x);
else printf("Mission impossible!\n");
}
return ;
}