2012-A3-0027

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<cstring>
#include<cassert>
using namespace std;
const char info[]="We need God's help!";
#define InCase(x) if(__builtin_expect((x),0))
const int dx[]= {0,1,0,-1},dy[]={1,0,-1,0};
int f[50][50][32],mx[8],my[8],g[50][50],n,m,o,l,xs,ys,xd,yd;
vector<int> old,xin;
inline int zt(int x,int y,int li,int fz){
    return ((x<<8|y)<<4|li)<<5|fz;
}
inline int mnst(int x,int y){
    for(int i=0;i<o;++i)
        if(x==mx[i]&&y==my[i])
            return i;
    return -1;
}
inline int calc(int t,int l){
    return (t<<8)-l;
}
int solve(){
    int tmp,tx,ty,tl,tz,x,y,li,fz;
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
            memset(f[i][j],0x3f,128);
    //f[xs][ys][0] = calc(0,0);
    old.clear();
    xin.clear();
    if(xs == xd && ys == yd)return 0;
    xin.push_back(zt(xs,ys,l,0));
    for(int turns=1;xin.size();++turns){
        xin.swap(old);
        for(;old.size();){
            x = (*old.rbegin())>>17&63;
            y = (*old.rbegin())>>9&63;
            li= (*old.rbegin())>>5&15;
            fz= (*old.rbegin())&31;
            InCase( ~(tmp = mnst(x,y)))
                fz|= 1<< tmp;
            old.pop_back();
            //printf("%d: X%d Y%d L%d Z%d\n",turns,x,y,li,fz);
            InCase(x == xd && y==yd)
                return turns;
            for(int i=0;i<4;++i){
                tx = x + dx[i];
                ty = y + dy[i];
                InCase(tx<0 || ty<0 || tx>=n || ty>=m || g[tx][ty]==-1)
                    continue;
                tl = li - 1;
                if(g[tx][ty] && !(fz&(1<<g[tx][ty]-1)))
                    tl =0;
                InCase(tx == xd && ty == yd)return turns;
                if(tl){
                    if(f[tx][ty][fz]>calc(turns,tl)){
                        old.push_back(zt(tx,ty,tl,fz));
                        f[tx][ty][fz]=calc(turns,tl);
                    }
                }else{
                    if(f[tx][ty][fz]> calc(turns + 1,l)){
                        xin.push_back(zt(tx,ty,l,fz));
                        f[tx][ty][fz]= calc(turns + 1,l);
                    }
                }
            }
        }
    }
    return ~0;
}
int main(){
    for(int ans,cnt =1;scanf("%d%d%d",&n,&m,&l)==3;++cnt){
        for(int i=0;i<n;++i)
            for(int j=0;j<m;++j)
                scanf("%d",&g[i][j]);
        scanf("%d",&o);
        for(int i =0;i<o;++i){
            scanf("%d%d",mx+i,my+i);
            --mx[i];--my[i];
        }
        scanf("%d%d%d%d",&xs,&ys,&xd,&yd);
        --xs;--ys;--xd;--yd;
        ~(ans = solve())? printf("%d\n",ans):puts(info);
        /*ans = solve();
        InCase(cnt == 13){
            printf("%d %d %d\n",n,m,l);
            for(int i=0;i<n;++i)
                for(int j=0;j<m;++j)
                    printf("%d%c",g[i][j],(j+1==m)?'\n':' ');
            printf("%d\n",o);
            for(int i =0;i<o;++i)
                printf("%d %d\n",mx[i]+1,1+my[i]);
            printf("%d %d %d %d\n",xs+1,ys+1,xd+1,yd+1);
            return 0;
        }*/
    }
    return 0;
}
}}}

#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<cstring>
#include<cassert>
using namespace std;
const char info[]="We need God's help!";
#define InCase(x) if(__builtin_expect((x),0))
const int dx[]= {0,1,0,-1},dy[]={1,0,-1,0};
int f[50][50][32],mx[8],my[8],g[50][50],n,m,o,l,xs,ys,xd,yd;
vector<int> old,xin;
inline int zt(int x,int y,int li,int fz){
    return ((x<<8|y)<<4|li)<<5|fz;
}
inline int mnst(int x,int y){
    for(int i=0;i<o;++i)
        if(x==mx[i]&&y==my[i])
            return i;
    return -1;
}
inline int calc(int t,int l){
    return (t<<8)-l;
}
int solve(){
    int tmp,tx,ty,tl,tz,x,y,li,fz;
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
            memset(f[i][j],0x3f,128);
    //f[xs][ys][0] = calc(0,0);
    old.clear();
    xin.clear();
    if(xs == xd && ys == yd)return 0;
    xin.push_back(zt(xs,ys,l,0));
    for(int turns=1;xin.size();++turns){
        xin.swap(old);
        for(;old.size();){
            x = (*old.rbegin())>>17&63;
            y = (*old.rbegin())>>9&63;
            li= (*old.rbegin())>>5&15;
            fz= (*old.rbegin())&31;
            InCase( ~(tmp = mnst(x,y)))
                fz|= 1<< tmp;
            old.pop_back();
            //printf("%d: X%d Y%d L%d Z%d\n",turns,x,y,li,fz);
            InCase(x == xd && y==yd)
                return turns;
            for(int i=0;i<4;++i){
                tx = x + dx[i];
                ty = y + dy[i];
                InCase(tx<0 || ty<0 || tx>=n || ty>=m || g[tx][ty]==-1)
                    continue;
                tl = li - 1;
                if(g[tx][ty] && !(fz&(1<<g[tx][ty]-1)))
                    tl =0;
                InCase(tx == xd && ty == yd)return turns;
                if(tl){
                    if(f[tx][ty][fz]>calc(turns,tl)){
                        old.push_back(zt(tx,ty,tl,fz));
                        f[tx][ty][fz]=calc(turns,tl);
                    }
                }else{
                    if(f[tx][ty][fz]> calc(turns + 1,l)){
                        xin.push_back(zt(tx,ty,l,fz));
                        f[tx][ty][fz]= calc(turns + 1,l);
                    }
                }
            }
        }
    }
    return ~0;
}
int main(){
    for(int ans,cnt =1;scanf("%d%d%d",&n,&m,&l)==3;++cnt){
        for(int i=0;i<n;++i)
            for(int j=0;j<m;++j)
                scanf("%d",&g[i][j]);
        scanf("%d",&o);
        for(int i =0;i<o;++i){
            scanf("%d%d",mx+i,my+i);
            --mx[i];--my[i];
        }
        scanf("%d%d%d%d",&xs,&ys,&xd,&yd);
        --xs;--ys;--xd;--yd;
        ~(ans = solve())? printf("%d\n",ans):puts(info);
        /*ans = solve();
        InCase(cnt == 13){
            printf("%d %d %d\n",n,m,l);
            for(int i=0;i<n;++i)
                for(int j=0;j<m;++j)
                    printf("%d%c",g[i][j],(j+1==m)?'\n':' ');
            printf("%d\n",o);
            for(int i =0;i<o;++i)
                printf("%d %d\n",mx[i]+1,1+my[i]);
            printf("%d %d %d %d\n",xs+1,ys+1,xd+1,yd+1);
            return 0;
        }*/
    }
    return 0;
}