题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4444
题目大意:
一些平行于坐标轴的矩形,给一个起点和终点(均不会在矩形内),求起点到终点需要转弯几次(不能穿过矩形).
题目思路:
只有50个矩形,但坐标最大为10^8,所以对坐标进行离散(x,y分别离散),
例如1,2,30,57,60,173 离散后应为,1,3,5,7,9,11,即每个相邻值都差2.
(1)由于建筑物的边缘可以走,所以对建筑物内的点设为4,边缘上的点+1(初始均为0), 易知边缘上的点最多被4个矩形覆盖.
(2)再把得到的图扫一遍,把和0相邻的点标为1,表示为最边缘的点,因为即使是最边缘的点(直接由0走到的点),在(1)的时候也可能+过1次以上,这样之后得到的图在不超过1的点均可以任意走,在2和3的点只能往某一方向拐,4的点是不能走的.
(3)最后求个最短路就ok.
ps:不知道为啥,之前的代码一段关键部分莫名其妙的消失了= =,判断2,3的可走方向,那部分,括号内的代码莫名消失...已补上
代码:
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <time.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define ls rt<<1
#define rs ls|1
#define lson l,mid,ls
#define rson mid+1,r,rs
#define middle l+r>>1
typedef pair<int,int> pii;
typedef multiset<int> mset;
typedef multiset<int>::iterator mst_it;
template <class T> T _max(T x,T y){return x>y? x:y;}
template <class T> T _min(T x,T y){return x<y? x:y;}
template <class T> void _swap(T &x,T &y){T z=x;x=y;y=z;}
template <class T> T GCD(T a,T b){for(T t;b;t=a%b,a=b,b=t);return a;}
template <class T> T LCM(T a,T b){return a/GCD(a,b)*b;}
#define clr_all(x,num) memset(x,num,sizeof(x))
#define clr(x,num,sz) memset(x,num,sizeof(x[0])*(sz+1))
#define inf 0x3F3F3F3F
#define eps (1e-9)
#define MOD 1000000007
const double pi=acos(-1.0);
const int M=500 +3;
int ts,cas=0;
int n,m,k;
int dis[M][M][4];
bool inq[M][M][4];
int X[M],Y[M],xm,ym;
map<int,int>hsx,hsy;
int maze[M][M],r,c;
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; //上下左右,正方向
int op[4]={1,0,3,2};下上右左
int ddir[4][2]={{-1,-1},{-1,1},{1,-1},{1,1}};//斜方向
int oop[4][2]={{2,3},{0,1},{1,3},{0,2}};//判断点为2和3时的可走方向时用,数字对应斜方向
int mp[4][2]={{2,3},{2,3},{0,1},{0,1}};//oop[i][j]可行,走mp[i][j],数字对应正方向
struct mtx{
int x1,y1,x2,y2;
int read(){
int res=scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(x1==y1 && x2==y2 && x1==0 && x2==0) res=-1;
return res;
}
}p[55];
struct node{
int x,y,d;
node(){}
node(int _x,int _y,int _d){x=_x,y=_y,d=_d;}
};
int spfa(int x,int y){
clr_all(dis,-1);
clr_all(inq,0);
queue<node>q;
int i,j;
for(i=0;i<4;i++){
q.push(node(x,y,i));
dis[x][y][i]=0;
}
while(!q.empty()){
node t=q.front();
q.pop(),inq[t.x][t.y][t.d]=0;
if(maze[t.x][t.y]>1){
for(j=0;j<2;j++){
x=t.x+ddir[oop[t.d][j]][0];
y=t.y+ddir[oop[t.d][j]][1];
if(!maze[x][y]){
x=t.x+dir[mp[t.d][j]][0];
y=t.y+dir[mp[t.d][j]][1];
int tmp=dis[t.x][t.y][t.d]+1;
i=mp[t.d][j];
if(dis[x][y][i]==-1 || dis[x][y][i]>tmp){
dis[x][y][i]=tmp;
if(!inq[x][y][i]) q.push(node(x,y,i)),inq[x][y][i]=1;
}
}
}
continue;
}
for(i=0;i<4;i++){
if(t.d==op[i]) continue;
x=t.x+dir[i][0];
if(x<0 || x>r) continue;
y=t.y+dir[i][1];
if(y<0 || y>c) continue;
if(maze[x][y]>3) continue;
int tmp=dis[t.x][t.y][t.d]+( (i!=t.d)? 1:0);
if(dis[x][y][i]==-1 || dis[x][y][i]>tmp){
dis[x][y][i]=tmp;
if(!inq[x][y][i]) q.push(node(x,y,i)),inq[x][y][i]=1;
}
}
}
int ans=-1,tx=hsx[p[0].x2],ty=hsy[p[0].y2];
for(i=0;i<4;i++) if(dis[tx][ty][i]!=-1){
if(ans==-1 || ans>dis[tx][ty][i])
ans=dis[tx][ty][i];
}
return ans;
}
void run(){
int i,j,k;
hsx.clear();
hsy.clear();
xm=ym=0;
X[++xm]=p[0].x1,X[++xm]=p[0].x2;
Y[++ym]=p[0].y1,Y[++ym]=p[0].y2;
scanf("%d",&n);
for(i=1;i<=n;i++){
p[i].read();
if(p[i].x1>p[i].x2) _swap(p[i].x1,p[i].x2);
if(p[i].y1>p[i].y2) _swap(p[i].y1,p[i].y2);
X[++xm]=p[i].x1,X[++xm]=p[i].x2;
Y[++ym]=p[i].y1,Y[++ym]=p[i].y2;
}
sort(X+1,X+xm+1);
sort(Y+1,Y+ym+1);
xm=unique(X+1,X+xm+1)-(X+1);
ym=unique(Y+1,Y+ym+1)-(Y+1);
for(i=1,r=1;i<=xm;i++,r+=2)
hsx[X[i]]=r;
for(i=1,c=1;i<=ym;i++,c+=2)
hsy[Y[i]]=c;
clr_all(maze,0);
for(i=1;i<=n;i++){
int x,y;
int x1=hsx[p[i].x1],y1=hsy[p[i].y1];
int x2=hsx[p[i].x2],y2=hsy[p[i].y2];
for(x=x1+1;x<x2;x++)
for(y=y1+1;y<y2;y++)
maze[x][y]=4;
for(y=y1;y<=y2;y++)
maze[x1][y]++,maze[x2][y]++;
for(x=x1+1;x<x2;x++)
maze[x][y1]++,maze[x][y2]++;
}
for(i=1;i<r;i++){
for(j=1;j<c;j++) if(maze[i][j]>1 && maze[i][j]<4){
int cnt=0;
for(k=0;k<4;k++){
if(!maze[i+dir[k][0]][j+dir[k][1]]){maze[i][j]=1;break;}
cnt++;
}
if(maze[i][j]==1) continue;
for(k=0;k<4;k++)
if(maze[i+ddir[k][0]][j+ddir[k][1]])
cnt++;
if(cnt==8) maze[i][j]=4;
}
}
int sx=hsx[p[0].x1],sy=hsy[p[0].y1];
int tx=hsx[p[0].x2],ty=hsy[p[0].y2];
printf("%d\n",spfa(hsx[p[0].x1],hsy[p[0].y1]));
}
void preSof(){
}
int main(){
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
preSof();
//run();
while(~p[0].read()) run();
//for(scanf("%d",&ts),cas=1;cas<=ts;cas++) run();
return 0;
}