首页 > ACM题库 > HDU-杭电 > HDU 4444-Walk-图-[解题报告]HOJ
2015
07-16

HDU 4444-Walk-图-[解题报告]HOJ

Walk

问题描述 :

Biaoge is planning to walk to amusement park. The city he lives can be abstracted as a 2D plane. Biaoge is at (x1, y1) and the amusement park is at (x2, y2). There are also some rectangle buildings. Biaoge can only walk parallel to the coordinate axis. Of course Biaoge can’t walk across the buildings.
What’s the minimum number of turns Biaoge need to make?
Lost

As the figure above shows, there are 4 buildings and Biaoge need to make at least 3 turns to reach the amusement park(Before walking he can chose a direction freely). It is guaranteed that all the buildings are parallel to the coordination axis. Buildings may contact but overlapping is impossible. The amusement park and Biaoge’s initial positions will not contact or inside any building.

输入:

There are multiple test case.
Each test case contains several lines.
The first line contains 4 integers x1, y1, x2, y2 indicating the coordinate of Biaoge and amusement park.
The second line contains one integer N(0≤N≤50), indicating the number of buildings.
Then N lines follows, each contains 4 integer x1, y1, x2, y2, indicating the coordinates of two opposite vertices of the building.
Input ends with 0 0 0 0, you should not process it.
All numbers in the input range from -108 to 108.

输出:

There are multiple test case.
Each test case contains several lines.
The first line contains 4 integers x1, y1, x2, y2 indicating the coordinate of Biaoge and amusement park.
The second line contains one integer N(0≤N≤50), indicating the number of buildings.
Then N lines follows, each contains 4 integer x1, y1, x2, y2, indicating the coordinates of two opposite vertices of the building.
Input ends with 0 0 0 0, you should not process it.
All numbers in the input range from -108 to 108.

样例输入:

0 0 0 10
1
0 5 5 8
0 0 0 10
2
0 5 5 8
-2 1 0 5
0 0 0 0

样例输出:

0
2
Hint
In the first case, Biaoge can walk along the side of building, and no turn needed. In the second case, two buildings block the direct way and Biaoge need to make 2 turns at least.

题意:问最少拐多少次弯可以从起点到终点。。

好难啊 ,可以从边界上经过的。第一次做这样的题。。。。

思路:把一个点拆成4个点。看每一个点的所有走法。

Walk

第一次画图,莫笑

#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <map>
#include <iostream>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N=109;
bool visit[N<<1][N<<1];
map<int,int> mpx;
map<int,int> mpy;
int n;
struct cpoint{
    int x,y;
    void get()
    {
         scanf("%d%d",&x,&y);x<<=1;y<<=1;
    }
} st,en,re[59][2];
int hashx[N<<1],hashy[N<<1],cnx,cny;
bool  can[N][N][4][4];
void init()
{
    mpx.clear();mpy.clear();
    memset(can,false,sizeof(can));
    cnx=0;cny=0;
    for(int i=0;i<n;i++)
    {
        hashx[cnx++] = re[i][0].x;
        hashx[cnx++] = re[i][0].x+1;
        hashx[cnx++] = re[i][1].x;
        hashx[cnx++] = re[i][1].x+1;
        hashy[cny++] = re[i][0].y;
        hashy[cny++] = re[i][0].y+1;
        hashy[cny++] = re[i][1].y;
        hashy[cny++] = re[i][1].y+1;
    }
    sort(hashx,hashx+cnx);sort(hashy,hashy+cny);
    int tx=0,ty=0;
    mpx[hashx[0]] = 0;
    mpy[hashy[0]] = 0;
    for(int i=1;i<cnx;i++)
    if(hashx[tx]!=hashx[i])
    {
        hashx[++tx] = hashx[i];
        mpx[hashx[i]] = tx;
    }
    for(int i=1;i<cny;i++)
    if(hashy[ty]!=hashy[i])
    {
        hashy[++ty] = hashy[i];
        mpy[hashy[i]] = ty;
    }
    cnx = tx+1,cny = ty+1;
    memset(visit,true,sizeof(visit));
    for(int i=1;i<n;i++)
    {
        int X = mpx[re[i][1].x],Y = mpy[re[i][1].y];
        for(int j=mpx[re[i][0].x]+1;j<=X;j++)
        for(int k=mpy[re[i][0].y]+1;k<=Y;k++)
        visit[j][k] = 0;
    }
    cnx>>=1;cny>>=1;
    for(int i=0;i<cnx;i++)
    for(int j=0;j<cny;j++)
    {
        if((visit[i<<1][j<<1]&&visit[i<<1][j<<1|1])||(visit[i<<1|1][j<<1]&&visit[i<<1|1][j<<1|1]))
            can[i][j][3][3] = can[i][j][1][1] = 1;
        if((visit[i<<1][j<<1]&&visit[i<<1|1][j<<1])||(visit[i<<1][j<<1|1]&&visit[i<<1|1][j<<1|1]))
            can[i][j][2][2] = can[i][j][0][0] = 1;
        if(visit[i<<1][j<<1])
            can[i][j][2][3] = can[i][j][1][0] = 1;
        if(visit[i<<1][j<<1|1])
            can[i][j][2][1] = can[i][j][3][0] = 1;
        if(visit[i<<1|1][j<<1])
            can[i][j][0][3] = can[i][j][1][2] = 1;
        if(visit[i<<1|1][j<<1|1])
            can[i][j][0][1] = can[i][j][3][2] = 1;
        if(visit[i<<1][j<<1]&&visit[i<<1][j<<1|1]&&visit[i<<1|1][j<<1])
            can[i][j][0][1] = can[i][j][3][2] = 1;
        if(visit[i<<1][j<<1]&&visit[i<<1][j<<1|1]&&visit[i<<1|1][j<<1|1])
            can[i][j][1][2] = can[i][j][0][3] = 1;
        if(visit[i<<1][j<<1]&&visit[i<<1|1][j<<1]&&visit[i<<1|1][j<<1|1])
            can[i][j][2][1] = can[i][j][3][0] = 1;
        if(visit[i<<1][j<<1|1]&&visit[i<<1|1][j<<1]&&visit[i<<1|1][j<<1|1])
            can[i][j][1][0] = can[i][j][2][3] = 1;
    }
}
queue<int> que;
bool oor(int x,int y)
{
    if(x<0||x>=cnx) return false;
    if(y<0||y>=cny) return false;
    return true;
}
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
int dis[N][N][4];

bool in[N][N][4];
void solve()
{
    memset(in,0,sizeof(in));
    memset(dis,INF,sizeof(dis));
    while(!que.empty()) que.pop();
    int stx=mpx[st.x]/2,sty=mpy[st.y]/2,enx=mpx[en.x]/2,eny=mpy[en.y]/2;
    for(int i=0;i<4;i++)
    {
        que.push((stx<<12)|(sty<<2)|i);
        dis[stx][sty][i]= 0;
    }
    while(!que.empty())
    {
        int e = que.front(); que.pop();
        int ed,ex,ey;
        ed = e&3;e>>=2;
        ey = e&1023;e>>=10;
        ex = e;
        in[ex][ey][ed] = false;
        for(int i=0;i<4;i++)
        {
            int tx=ex+dx[i],ty=ey+dy[i];
            if(i==ed&&oor(tx,ty)&&can[ex][ey][ed][i]&&dis[tx][ty][i]>dis[ex][ey][ed])
            {
                dis[tx][ty][i]=dis[ex][ey][ed];
                if(!in[tx][ty][i]) que.push((tx<<12)|(ty<<2)|i);
            }
            else if(i!=ed&&oor(tx,ty)&&can[ex][ey][ed][i]&&dis[tx][ty][i]>dis[ex][ey][ed]+1)
            {
                dis[tx][ty][i]=dis[ex][ey][ed]+1;
                if(!in[tx][ty][i]) que.push((tx<<12)|(ty<<2)|i);
            }
        }
    }
    int ans=INF;
    for(int i=0;i<4;i++)
    ans = min(dis[enx][eny][i],ans);
    printf("%d\n",ans==INF?-1:ans);
}
int main()
{
    freopen("in.txt","r",stdin);
    while(~scanf("%d%d%d%d",&st.x,&st.y,&en.x,&en.y))
    {
        if(st.x==0&&st.y==0&&en.x==0&&en.y==0) break;
        st.x<<=1;st.y<<=1;en.x<<=1;en.y<<=1;
        re[0][0] = st;
        re[0][1] = en;
        scanf("%d",&n);n+=1;
        for(int i=1;i<n;i++)
        {
            re[i][0].get(),re[i][1].get();
            if(re[i][0].x>re[i][1].x) swap(re[i][0].x,re[i][1].x);
            if(re[i][0].y>re[i][1].y) swap(re[i][0].y,re[i][1].y);
        }
        init();
        solve();
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/binwin20/article/details/8183782


,