2013年8月7日 星期三

2013/8/7 icpcarchive 3274 - Crossing Streets

/* https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=39&page=show_problem&problem=1275 */
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <queue>
#include <map>
using namespace std;
int XMAX, YMAX, m[2000][2000];
map <int ,int>xmap; map <int ,int>ymap;
bool cmp(int a, int b)
{
    return a < b;
}
struct xy
{
    int x, y;
};
queue<xy> next; queue<xy> now;
int X[] ={ 1, 0, -1 ,0}; int Y[] ={ 0, 1, 0, -1};
void draw()
{
    while( !now.empty() )
    {

        xy TOP = now.front(); now.pop();
            for( int j = 0; j < 4 ; j++)
            {

                xy t = TOP; t.x = TOP.x+X[j]; t.y = TOP.y+Y[j];
              //  cout<<"OP "<<XMAX<<" "<<YMAX<<endl;
              //   cout<<"UD"<<" "<<t.x<<" "<<t.y<<" "<<m[ t.x ][ t.y ]<<endl;
                if( 0 <= t.x && t.x < XMAX &&
                    0 <= t.y && t.y < YMAX &&
                    m[ t.x ][ t.y ] != 1
                    )
                  {

                      if( m[ t.x ][ t.y ] == 0 ){ m[ t.x ][ t.y ] = 1; now.push(t); }
                      else if( m[ t.x ][ t.y ] == -1 ){ m[ t.x ][ t.y ] = 1; next.push(t); }
                  }
            }

    }
}
int main()
{
    int n;  int sx[2000], sy[2000], xi, yi;
    int mx, my, dx, dy; int tx[2000], txi, ty[2000], tyi;
    xy LINE1[2000]; xy LINE2[2000]; int cnt = 0;
    while( scanf("%d", &n) )
    {
        cnt++;
        xmap.clear(); ymap.clear();
        xi = yi = 0;
        txi = tyi = 0;

        if( n == 0 ) break;
        for(int i = 0; i < n; i++)
        {
            int x1, y1, x2, y2;
            scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
            sx[xi++] = x1; sx[xi++] = x2;
            sy[yi++] = y1; sy[yi++] = y2;
            LINE1[i].x = x1; LINE1[i].y = y1;
            LINE2[i].x = x2; LINE2[i].y = y2;
        }
        scanf("%d %d %d %d", &mx, &my, &dx, &dy);
        sx[xi++] = mx; sx[xi++] = dx;
        sy[yi++] = my; sy[yi++] = dy;
        sort( sx, sx+xi, cmp); sort( sy, sy+yi, cmp);


        tx[txi] = sx[0];
        xmap.insert(pair< int , int>( sx[0], txi)); txi++;

        for(int i = 1; i < xi; i++)
        {
            if( sx[i] != sx[i-1] )
            {
                tx[txi] = sx[i];
                xmap.insert(pair< int , int>( sx[i], txi));
                txi++;
            }
        }


        ty[tyi] = sy[0];
        ymap.insert(pair< int , int>( sy[0], tyi)); tyi++;

        for(int i = 1; i < yi; i++)
        {
            if( sy[i] != sy[i-1] )
            {
                ty[tyi] = sy[i];
                ymap.insert(pair< int , int>( sy[i], tyi));
                tyi++;
            }
        }
          //cout<<"YYY"<<" "<<txi<<" "<<tyi<<endl;
        XMAX = txi; YMAX = tyi;
        for(int i = 0; i < XMAX; i++)
            for(int j = 0; j < YMAX; j++)
                m[i][j] = 0;
         //cout<< m[ xmap[mx] ][ ymap[my] ]<<endl;

        for(int i = 0; i < n; i++)
        {
            if( LINE1[i].x == LINE2[i].x )
            {
                int mn = min(LINE1[i].y, LINE2[i].y);
                int mx = max(LINE1[i].y, LINE2[i].y);
                for(int j = ymap[mn]; j <= ymap[mx]; j++)
                    m[ xmap[LINE1[i].x] ][ j ] = -1;
            }else
            {
                int mn = min(LINE1[i].x, LINE2[i].x);
                int mx = max(LINE1[i].x, LINE2[i].x);
                for(int j = xmap[mn]; j <= xmap[mx]; j++)
                    m[ j ][ ymap[LINE1[i].y] ] = -1;
            }
        }

        while( !now.empty() ){ now.pop(); }
        while( !next.empty() ){ next.pop(); }
        m[ xmap[dx] ][ ymap[dy] ] = 1; int ans = -1;
        xy op; op.x= xmap[dx]; op.y = ymap[dy]; now.push(op);
        //cout<< XMAX<<" "<<YMAX<<endl;
       // cout<< xmap[mx]<<" "<<ymap[my]<<endl;
        while( m[ xmap[mx] ][ ymap[my] ] == 0 )
        {
            ans ++;
            draw();
            while( !next.empty() )
            {
                now.push(next.front()); next.pop();
            }//cout<<"XDDDDDDD\n";
        }
        printf("City %d\n", cnt);
        printf("Peter has to cross %d streets\n", ans);
       // printf("%d\n", ans);
    }
}

沒有留言:

張貼留言