ACM/ICCC 2012金華regionalフィールド試合C題hdu 4444離散化、最短

2012/12/31修正.最も主要なのは角点が通らない問題を修正し、格子を8つに分けて特判した.例えば、ある格子の左下、右下、左上の格子が黒い格子であれば、この角点は「L」の形をしているので、状態5にします.では、この格子では、上と右だけが格子に入ることができ、右から格子に入ると上だけが格子から離れることができ、上から入ると右だけが離れることができます.
これらの判定は、2つの関数check 3(格子状態、進入方向)とcheck 2(格子状態、進入方向、離間方向)によって判定される.また,離散化された座標を小さく修正し,始点終点の座標も離散に加えることで,ans=0を特判する必要がなくなる.修正されたプログラムは、0-12 1 3-1 0 0 1 0 1 1 2 1-2 3 0正解が1です.コーナーポイントを通ります.修正したプログラムはHDUACで可能になりました.でも、使う時はちょっと多いです.の修正コードは次のとおりです.

#include
#include
#include
#include
#include
using namespace std;
#define NN 400
#define INF 100000000


int stx,sty,edx,edy;
int n,tx,ty,sx[NN],sy[NN],a,b,c,d,ttx,tty,i,ans,flag;
int dis[NN][NN][5],inq[NN][NN][5],g[NN][NN];
int dx[]={0,1,0,-1};//        
int dy[]={1,0,-1,0};

struct point {
    int x,y;
    void init(int _x,int _y){x=_x;y=_y;};
}bu[NN][10];
  

int bsch1(int val,int v[],int l,int r){//          ，        
    int mid;
    while(l<=r){
       mid=(l+r)>>1;
       if (v[mid]==val) return mid;
       if (v[mid] qx,qy,qd;
    for(j=0;j<4;j++){dis[stx][sty][j]=0;qx.push(stx);qy.push(sty);qd.push(j);inq[stx][sty][j]=1;}
    while(!qx.empty()){
        ux=qx.front();qx.pop();uy=qy.front();qy.pop();ud=qd.front();qd.pop();
        inq[ux][uy][ud]=0;
        for(dir=0;dir<4;dir++)if (check2(g[ux][uy],ud,dir)){
           vx=ux+dx[dir];vy=uy+dy[dir];vd=dir;
           if (vx>=1&&vx<=tx&&vy>=1&&vy<=ty&&check3(g[vx][vy],vd)&&dis[vx][vy][vd]>dis[ux][uy][ud]+(ud==vd?0:1)){
                 dis[vx][vy][vd]=dis[ux][uy][ud]+(ud==vd?0:1);
                 if (!inq[vx][vy][vd]){
                    inq[vx][vy][vd]=1;
                    qx.push(vx);qy.push(vy);qd.push(vd);
                 }
           }
        }
    }
    int ans=INF;
    for(j=0;j<4;j++){
       if (ans>dis[edx][edy][j]) ans=dis[edx][edy][j];
    }
    return ans;
}
    
void add(int a,int b,int c,int d){//       ，+1，-1       
     sx[++tx]=a;sx[++tx]=a-1;sx[++tx]=a+1;
     sx[++tx]=c;sx[++tx]=c-1;sx[++tx]=c+1;
     sy[++ty]=b;sy[++ty]=b-1;sy[++ty]=b+1;
     sy[++ty]=d;sy[++ty]=d-1;sy[++ty]=d+1;
}

inline bool cmp1(int x,int y){return x10000000) ans=-1;//          -1           
        printf("%d
",ans);
    }
    return 0;
}
        

________________________________________________________________________________________________________________
現場試合は血で虐げられた.弱すぎます.
この問題は明らかに離散化して図を建てて、spfaで最短路を求めます.
しかし、いくつかの葛藤点があります.1.点は矩形のエッジxまたはy座標と同じです.この点について、私のやり方は座標に3を乗じることです.実は2を乗じてもいいです.座標を追加するたびに、座標を×3、座標を×3＋1、座標×3、座標×3−1はいずれも添加して離散した.
2.長方形の表示方法.私は最初は矩形を4つのエッジとして愚かに表現し、移動するたびにエッジのバリアがあるかどうかを判断する必要があります.チームメイトの注意で長方形の被覆領域を黒く塗るのが私のやり方です(1と表記)では、その点が到達するか否かを判断するだけです.矩形を黒く塗るたびに、矩形の左境界+1、右境界-1、上下境界も同様にします.これで矩形の境界は移動できます.しかし、隣接する2つの矩形がある場合、それらの境界は移動できません...では、このように判断できます.1つの点を切ります:もしその左と右がすべて黒いならば、それも黒いです、(上下、左上右下、左下右上同理).黒を表示し終わったら、簡単な最短処理を行うことができます.
3.もう一つ、答えが0の場合、つまり回転していない場合は、離散前の起点終点座標が同じかどうかを判断し、異なる場合は1回回転する.答えが0でなければ、これ以上回転する必要はありません.自分で絵を描いてみてもいいです.
次回はブロンズじゃなくて頑張って欲しいなぁ～

#include
#include
#include
#include
#include
using namespace std;
#define NN 400
#define INF 100000000


int stx,sty,edx,edy;
int n,tx,ty,sx[NN],sy[NN],a,b,c,d,ttx,tty,i,ans,flag;
int dis[NN][NN][5],inq[NN][NN][5],g[NN][NN];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};

struct point {
    int x,y;
    void init(int _x,int _y){x=_x;y=_y;};
}bu[NN][10];
  

int bsch1(int val,int v[],int l,int r){//          ，        
    int mid;
    while(l<=r){
       mid=(l+r)>>1;
       if (v[mid]==val) return mid;
       if (v[mid]>1;
        if (v[mid]==val) return mid;
        if (v[mid]>val) {if (ans>mid) ans=mid;r=mid-1;}
        else l=mid+1;
     }
     return ans;
}

inline void check(int i,int j){ //        
     if (g[i-1][j]&&g[i+1][j]) g[i][j]=1;
     if (g[i][j-1]&&g[i][j+1]) g[i][j]=1;
     if (g[i-1][j-1]&&g[i+1][j+1]||g[i+1][j-1]&&g[i-1][j+1]) g[i][j]=1;
}

void make_graph(){//  ，        
     int i,j,k,tmpx1,tmpx2,tmpy1,tmpy2;
     memset(g,0,sizeof(g));
     for(i=1;i<=n;i++){
        tmpx1=bsch1(bu[i][1].x+1,sx,1,tx);tmpx2=bsch1(bu[i][3].x-1,sx,1,tx);
        tmpy1=bsch1(bu[i][1].y+1,sy,1,ty);tmpy2=bsch1(bu[i][3].y-1,sy,1,ty);
        
        for(j=tmpx1;j<=tmpx2;j++)
          for(k=tmpy1;k<=tmpy2;k++)
             g[j][k]=1;
     }
     
     for(i=2;i qx,qy,qd;
    for(j=0;j<4;j++){dis[stx][sty][j]=0;qx.push(stx);qy.push(sty);qd.push(j);inq[stx][sty][j]=1;}
    while(!qx.empty()){
        ux=qx.front();qx.pop();uy=qy.front();qy.pop();ud=qd.front();qd.pop();
        inq[ux][uy][ud]=0;
        for(dir=0;dir<4;dir++){
           vx=ux+dx[dir];vy=uy+dy[dir];vd=dir;
           if (vx>=1&&vx<=tx&&vy>=1&&vy<=ty&&g[vx][vy]==0&&dis[vx][vy][vd]>dis[ux][uy][ud]+(ud==vd?0:1)){
                 dis[vx][vy][vd]=dis[ux][uy][ud]+(ud==vd?0:1);
                 if (!inq[vx][vy][vd]){
                    inq[vx][vy][vd]=1;
                    qx.push(vx);qy.push(vy);qd.push(vd);
                 }
           }
        }
    }
    int ans=INF;
    for(j=0;j<4;j++){
       if (ans>dis[edx][edy][j]) ans=dis[edx][edy][j];
    }
    return ans;
}
    
     
        

void add(int a,int b,int c,int d){//       ，+1，-1       
     sx[++tx]=a;sx[++tx]=a-1;sx[++tx]=a+1;
     sx[++tx]=c;sx[++tx]=c-1;sx[++tx]=c+1;
     sy[++ty]=b;sy[++ty]=b-1;sy[++ty]=b+1;
     sy[++ty]=d;sy[++ty]=d-1;sy[++ty]=d+1;
}

inline bool cmp1(int x,int y){return x10000000) ans=-1;//          -1           
        printf("%d
",ans);
    }
    return 0;
}