洛谷P 1979華容道題解

ピューピューピューピューピューピューピューピューピューピューピューピューピューピューピューピューピューピューピューピューピューピューピューピューピューピューピューピューピューピューピューピューピューピューピューピュー
洛谷P 1979華容道題解
NOIP 2018まであと7日で問題解を書いて人柄を蓄える
(初めて紫問題の問題解を書いたのはまだ少し興奮している)
いくつかの説明
1、本題解とコード中の0/1/2/3はそれぞれ上/下/左/右を表す
2、明確な表現のために、問題解には目標駒(タイトルの中の(SX,SY)が(B)、目標格子(タイトルの中の(TX,TY)が)(C)、空白格子が(E)
【考え方分析】何人かのdalaoが言ったように、この問題の建図は実行可能な状態をエッジにつなぎ、質問するたびに最短ルートを走ることである.
私が$ok[i][j][0/1/2/3]$で(B)が点((i,j))にある場合、4方向に空き格子がある可能性があるかどうか(各グループのクエリで空き格子が到達できるかどうかは考慮せず、その格子が固定格子であるかどうか、または境界を越えているかどうかのみを考慮する.)
このセクションのコードは次のとおりです.

//           
    for(int i=1;i<=n;i++)//           
    for(int j=1;j<=m;j++){
        if(!mapp[i][j])continue;//        
        for(int k=0;k<4;k++)//     
        if(judge(i+xx[k],j+yy[k]))ok[i][j][k]=1;
        }

judge関数は、空白または境界であるかどうかを判断するために使用されます.

bool judge(int ax,int ay){
    if(ax<=0||ax>n||ay<=0||ay>m)return 0;//   
    return mapp[ax][ay];
}

図面を作成するために、私は状態を1次元配列に保存します:格子の番号:上から下へ左から右へ編みます
\(e.g.\)

1 2 3 4

5 6 7 8

……

ステータスの番号(e.g.)
1番グリッドの4つのステータス番号は0123です.
すると、次の番号付け関数が得られます.

int getnum(int ax,int ay,int t){
    return ((ax-1)*m+ay)*4-(4-t);
}//t=0/1/2/3

(q)グループが尋ねる地図の状況は同じなので、先に図を建てることができます.
どのような2つの状態がエッジをつなぐことができますか?
2つの状況を考慮します.
・空白の格子が(B)を上下左右にぐるぐる回っている
bfsで乱転が少なくとも何回上から下へ、左から右へ...
注意が必要なのは、乱転時(B)は動けません!!!(ここは長い間QQQQをしていました)
・空白格子と(B)交換位置
両方のステータスが存在することを保証する必要があります.
距離1の辺をつなげてください.

int bfs(int dx,int dy,int sx,int sy,int tx,int ty){//            
    //(sx,sy)   (tx,ty)，    (dx,dy)
    queueq;
    memset(vis,0,sizeof vis);
    white st;st.x=sx;st.y=sy;
    st.step=0;vis[sx][sy]=1;
    q.push(st);
    while(!q.empty()){
        white noww=q.front();
        q.pop();
        if(noww.x==tx&&noww.y==ty)//       
        return noww.step;
        for(int i=0;i<4;i++){//       
            if(judge(noww.x+xx[i],noww.y+yy[i])){//     
                if(vis[noww.x+xx[i]][noww.y+yy[i]])continue;//     
                if(noww.x+xx[i]==dx&&noww.y+yy[i]==dy)continue;//         
                white nxt;
                nxt.x=noww.x+xx[i];
                nxt.y=noww.y+yy[i];
                nxt.step=noww.step+1;
                q.push(nxt);vis[noww.x+xx[i]][noww.y+yy[i]]=1;
            }
        }
    }
    return inf;//    
}

駒が動かず、空白格が乱転する場合:

    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    for(int k=0;k<4;k++)
    for(int l=k+1;l<4;l++){
        if(ok[i][j][k]&&ok[i][j][l]){//       
            int aa=getnum(i,j,k);
            int bb=getnum(i,j,l);
            int cc=bfs(i,j,i+xx[k],j+yy[k],i+xx[l],j+yy[l]);
            if(cc==inf)continue;
            add(aa,bb,cc);add(bb,aa,cc);
        }
    }

qwq

    for(int i=1;i<=n;i++)//            
    for(int j=1;j

これで初期化が完了しました!(プラスエッジの操作は普通の図論と同じw)
各グループの質問について、まず特審します.

while(q--){
        scanf("%d%d%d%d%d%d",&ex,&ey,&bx,&by,&cx,&cy);
        if(bx==cx&&by==cy){
            puts("0");
            continue;
        }
        if(!mapp[cx][cy]){
            puts("-1");
            continue;
        }
        if(!mapp[bx][by]){
            puts("-1");
            continue;
        }
        work();
    }

そして、最初の状態をどのように図に移すかを考えます.
空白格が(B)に隣接する状況しか存在しないので、so暴力は空白格を(B)の4つの方向に走らせようと試みるとよい

    for(int i=0;i<4;i++){//           
        if(judge(bx+xx[i],by+yy[i])){//       
            int nw=bfs(bx,by,ex,ey,bx+xx[i],by+yy[i]);
            if(nw==inf)continue;//    
            int nq=getnum(bx,by,i);
            d[nq]=nw;
            Q.push(nq);
            viss[nq]=1;
        }
    }

そして、楽しくSPFAを走ります

    while(!Q.empty()){
        int noww=Q.front();Q.pop();viss[noww]=0;
        for(int j=head[noww];j;j=b[j].nxt){
            int vv=b[j].to;
            if(d[vv]>d[noww]+b[j].dis){
                d[vv]=d[noww]+b[j].dis;
                if(!viss[vv])Q.push(vv),viss[vv]=1;
            }
        }
    }

最後に、到着できるかどうかを楽しくチェックします(C)

    int ans=inf;
    for(int i=0;i<4;i++){
        int qaq=getnum(cx,cy,i);
        ans=min(ans,d[qaq]);
    }
    if(ans==inf)puts("-1");
    else printf("%d
",ans);

アノテーションコードQWQを貼る

#include
using namespace std;
const int MAXN=35;
const int inf=99999999;
int n,m,q,ex,ey,bx,by,cx,cy;
bool mapp[MAXN][MAXN];
int xx[4]={-1,1,0,0};
int yy[4]={0,0,-1,1};
int getnum(int ax,int ay,int t){
    return ((ax-1)*m+ay)*4-(4-t);
} 
struct white{
    int x,y;
    int step;
};
bool judge(int ax,int ay){
    if(ax<=0||ax>n||ay<=0||ay>m)return 0;
    return mapp[ax][ay];
}
bool vis[MAXN][MAXN];
int bfs(int dx,int dy,int sx,int sy,int tx,int ty){
    queueq;
    memset(vis,0,sizeof vis);
    white st;st.x=sx;st.y=sy;
    st.step=0;vis[sx][sy]=1;
    q.push(st);
    while(!q.empty()){
        white noww=q.front();
        q.pop();
        if(noww.x==tx&&noww.y==ty)
        return noww.step;
        for(int i=0;i<4;i++){
            if(judge(noww.x+xx[i],noww.y+yy[i])){
                if(vis[noww.x+xx[i]][noww.y+yy[i]])continue;
                if(noww.x+xx[i]==dx&&noww.y+yy[i]==dy)continue; 
                white nxt;
                nxt.x=noww.x+xx[i];
                nxt.y=noww.y+yy[i];
                nxt.step=noww.step+1;
                q.push(nxt);vis[noww.x+xx[i]][noww.y+yy[i]]=1;
            }
        }
    }
    return inf;
}
struct edge{
    int to,nxt,dis;
}b[5005];
int head[5005],tot;
void add(int u,int v,int w){
    b[++tot].to=v;b[tot].nxt=head[u];
    b[tot].dis=w;head[u]=tot;
}
bool ok[MAXN][MAXN][5];
void init(){
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        if(!mapp[i][j])continue;
        for(int k=0;k<4;k++)
        if(judge(i+xx[k],j+yy[k]))ok[i][j][k]=1;
        }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    for(int k=0;k<4;k++)
    for(int l=k+1;l<4;l++){
        if(ok[i][j][k]&&ok[i][j][l]){
            int aa=getnum(i,j,k);
            int bb=getnum(i,j,l);
            int cc=bfs(i,j,i+xx[k],j+yy[k],i+xx[l],j+yy[l]);
            if(cc==inf)continue;
            add(aa,bb,cc);add(bb,aa,cc);
        }
    }
    for(int i=1;i<=n;i++)
    for(int j=1;jQ;
bool viss[5005];
int d[5005];
void work(){
    memset(d,128/3,sizeof d);
    memset(viss,0,sizeof viss);
    for(int i=0;i<4;i++){
        if(judge(bx+xx[i],by+yy[i])){
            int nw=bfs(bx,by,ex,ey,bx+xx[i],by+yy[i]);
            if(nw==inf)continue; 
            int nq=getnum(bx,by,i);
            d[nq]=nw;
            Q.push(nq);
            viss[nq]=1;
        }
    }
    while(!Q.empty()){
        int noww=Q.front();Q.pop();viss[noww]=0;
        for(int j=head[noww];j;j=b[j].nxt){
            int vv=b[j].to;
            if(d[vv]>d[noww]+b[j].dis){
                d[vv]=d[noww]+b[j].dis;
                if(!viss[vv])Q.push(vv),viss[vv]=1;
            }
        }
    }
    int ans=inf;
    for(int i=0;i<4;i++){
        int qaq=getnum(cx,cy,i);
        ans=min(ans,d[qaq]);
    }
    if(ans==inf)puts("-1");
    else printf("%d
",ans);
}
int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)cin>>mapp[i][j];
    init();
    while(q--){
        scanf("%d%d%d%d%d%d",&ex,&ey,&bx,&by,&cx,&cy);
        if(bx==cx&&by==cy){
            puts("0");
            continue;
        }
        if(!mapp[cx][cy]){
            puts("-1");
            continue;
        }
        if(!mapp[bx][by]){
            puts("-1");
            continue;
        }
        work();
    }
    return 0;
}

终わって花を撒きます!!!
by Erutsiom
転載先:https://www.cnblogs.com/erutsiom/p/9904567.html