题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=4444
题意：给你一些n个矩形，给你一个起点，一个终点，要你求从起点到终点最少需要转多少个弯
题解：因为矩形数量很少50个，可以离散化成102*102的坐标，但是人可以贴着墙壁走，但不能穿过墙壁
所以每个点要分成9等分。建筑物的边占1/3，但是这样有漏洞。
1、当两个墙壁贴在一起，中间还可以过，所以要填补中间
2、当两个矩形的角重合，中间也可以过，要填补中间，但是只能填补中间一个点，不能填补全部的9个点。
还有一点要注意的是，起点有多个，终点也有多个，从任意一起点到任意一终点即可，因为有一些特殊数据，我的例子里面有
图建好了，直接BFS记忆化搜索即可。
AC代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
#include <sstream>
using namespace std;
typedef long long LL;
const int N=410;
const LL II=100000000;
const int INF=0x3f3f3f3f;
const int M=12345678;
const double PI=acos(-1.0);
int sx,sy,ex,ey;
int si,sj,ei,ej;
int n,nx,ny;
int x[N],y[N];
int g[N][N],step[N][N];
int t[4][2]={1,0,-1,0,0,1,0,-1};
struct node
{
int x1,x2,y1,y2;
}rect[N];
struct xiaohao
{
int xx,yy;
int step;
}e,w,xh[M];
int nextint()
{
int f=1;
char c;
while((c=getchar())<'0'||c>'9')
if(c=='-')
f=-1;
int sum=c-'0';
while((c=getchar())>='0'&&c<='9')
sum=sum*10+c-'0';
return sum*f;
}
void lisanhua(int m) //离散化
{
int i,j;
sort(x+1,x+m+1);
sort(y+1,y+m+1);
nx=1;
for(i=2;i<=m;i++)//去重
if(x[i]!=x[i-1])
x[++nx]=x[i];
ny=1;
for(i=2;i<=m;i++)//去重
if(y[i]!=y[i-1])
y[++ny]=y[i];
}
int getx(int xx)//数据量大的时候可以用二分查找
{
for(int i=1;i<=nx;i++)
if(x[i]==xx)
return i;
}
int gety(int yy)
{
for(int i=1;i<=ny;i++)
if(y[i]==yy)
return i;
}
void add(int x1,int x2,int y1,int y2)
{
int i,j;
for(i=x1;i<=x2;i++)
for(j=y1;j<=y2;j++)
g[i][j]=1;//建筑物标记为1
}
void jiantu()
{
int i,j,x1,x2,y1,y2;
memset(g,0,sizeof(g));
si=getx(sx);
sj=gety(sy);
ei=getx(ex);
ej=gety(ey);
for(i=si*3;i>=si*3-2;i--)//起点,这个地方9个格子全部要标记为5
for(j=sj*3;j>=sj*3-2;j--)
g[i][j]=5;
for(i=ei*3;i>=ei*3-2;i--)//终点,这个地方9个格子全部要标记为6
for(j=ej*3;j>=ej*3-2;j--)
g[i][j]=6;
for(i=1;i<=n;i++)
{
x1=getx(rect[i].x1);
y1=gety(rect[i].y1);
x2=getx(rect[i].x2);
y2=gety(rect[i].y2);
add(x1*3,x2*3-2,y1*3,y2*3-2);
}
for(i=1;i<=nx;i++)//将重合的点中间补上
for(j=1;j<=ny;j++)
{
if(g[i*3-2][j*3-2]==1&&g[i*3][j*3]==1||g[i*3-2][j*3]==1&&g[i*3][j*3-2]==1)
g[i*3-1][j*3-1]=1;
if(g[i*3-1][j*3-2]==1&&g[i*3-1][j*3]==1)
g[i*3-1][j*3-1]=1;
if(g[i*3-2][j*3-1]==1&&g[i*3][j*3-1]==1)
g[i*3-1][j*3-1]=1;
}
// for(i=1;i<=3*nx;i++) //输出离散化后的图
// {
// for(j=1;j<=3*ny;j++)
// printf("%d",g[i][j]);
// printf("
");
// }
}
bool ok(int tx,int ty)
{
return (tx>=0&&tx<=3*nx&&ty>=0&&ty<=3*ny);
}
void BFS()
{
int i,j,head=0,tail=0;
w.step=-1;
for(i=si*3;i>=si*3-2;i--)
for(j=sj*3;j>=sj*3-2;j--)
if(g[i][j]==5)
{
w.xx=i;w.yy=j;
xh[tail++]=w;
}
memset(step,INF,sizeof(step));
step[w.xx][w.yy]=-1;
while(head!=tail)
{
e=xh[head++];
if(head==M)
head=0;
for(i=0;i<4;i++)
{
w=e;
w.step++;
int tx=w.xx+t[i][0];
int ty=w.yy+t[i][1];
while(ok(tx,ty)&&g[tx][ty]!=1)//判断是否在界内，而且能走
{
if(w.step<step[tx][ty])
{
if(g[tx][ty]==6)
{
printf("%d
",w.step);
return ;
}
step[tx][ty]=w.step;
w.xx=tx;
w.yy=ty;
xh[tail++]=w;
if(tail==M)
tail=0;
}
tx+=t[i][0];
ty+=t[i][1];
}
}
}
printf("-1
");
}
int main()
{
int i,j;
while(scanf("%d%d%d%d",&sx,&sy,&ex,&ey))
{
int x1,x2,y1,y2,m;
if((!sx)&&(!sy)&&(!ex)&&(!ey))
break;
if(sx==ex&&sy==ey)
{
printf("0
");
continue;
}
m=0;
rect[0].x1=x[++m]=sx;
rect[0].y1=y[m]=sy;
rect[0].x2=x[++m]=ex;
rect[0].y2=y[m]=ey;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(x1>x2)//防止有的数据先是右上点再是左下点
swap(x1,x2),swap(y1,y2);
x[++m]=rect[i].x1=x1;
y[m]=rect[i].y1=y1;
x[++m]=rect[i].x2=x2;
y[m]=rect[i].y2=y2;
}
lisanhua(m);
jiantu();
BFS();
}
return 0;
}
/*
0 0 3 3
4
2 0 4 2
0 2 2 4
4 2 6 4
2 4 4 6
100 -50 10 20
4
-100 15 -20 30
-5 25 50 100
-30 -30 70 -20
70 -20 120 80
5 -1 60 7
3
1 8 101 888
0 0 49 5
50 0 100 6
0 -1 2 1
3
-1 0 0 1
0 1 1 2
1 -2 3 0
0 0 0 10
1
0 5 5 8
0 0 0 10
1
-3 5 0 8
0 0 0 10
2
0 5 5 8
0 2 4 5
0 0 0 10
2
0 5 5 8
-2 1 0 4
0 0 0 10
2
0 0 5 8
-2 1 0 5
0 0 1 10
0
0 -1 2 1
3
-1 0 0 1
0 1 1 2
1 -2 3 0
0 -1 -1 0
9
-3 4 4 5
4 -3 5 5
-2 -3 4 -2
-3 -3 -2 4
-1 2 0 4
1 1 3 3
0 0 1 1
-2 -2 0 0
2 -2 3 0
0 0 0 0
结果应该为：
-1
3
2
1
0
0
0
0
2
1
1
5
*/