NOIP2013 华容道 (棋盘建图+spfa最短路)

时间:2022-12-16 15:08:11
  1 #include <cstdio>
  2 #include <algorithm>
  3 #include <cstring>
  4 #include <queue>
  5 #define inf 0x3f3f3f3f
  6 #define N 35
  7 #define maxn 5000
  8 #define mod 1000000007
  9 #define ll long long 
 10 using namespace std;
 11 
 12 int n,m,q,cte;
 13 int ok[N][N],id[N][N],head[maxn],dis[maxn],inq[maxn],st[4];
 14 int xx[]={-1,0,1,0};
 15 int yy[]={0,1,0,-1};
 16 struct EDGE{
 17     int to,nxt,val;
 18 }edge[maxn*500];
 19 struct node{
 20     int x,y;
 21 };
 22 node ins(int s1,int s2) {node k;k.x=s1;k.y=s2;return k;}
 23 bool check(int x,int y)
 24 {
 25     if(x<1||y<1||x>n||y>m||!ok[x][y]) return false;
 26     else return true;
 27 }
 28 void edge_add(int u,int v,int w)
 29 {
 30     cte++;
 31     edge[cte].to = v;
 32     edge[cte].nxt=head[u];
 33     edge[cte].val= w;
 34     head[u]=cte;
 35 }
 36 void bfs(int ex,int ey,int sx,int sy,int d)
 37 {
 38     queue<node>q;
 39     memset(dis,-1,sizeof(dis));
 40     dis[id[ex][ey]]=0,dis[id[sx][sy]]=1;
 41     q.push(ins(ex,ey));
 42     int x,y,fx,fy;
 43     while(!q.empty())
 44     {
 45         node k=q.front();q.pop();
 46         x=k.x,y=k.y;
 47         for(int i=0;i<4;i++)
 48         {
 49             fx=x+xx[i],fy=y+yy[i];
 50             if(!check(fx,fy)||dis[id[fx][fy]]!=-1) continue;
 51             dis[id[fx][fy]]=dis[id[x][y]]+1;
 52             q.push(ins(fx,fy));
 53         }
 54     }
 55     for(int i=0;i<4;i++)
 56     {
 57         fx=sx+xx[i],fy=sy+yy[i];
 58         if(!check(fx,fy)||dis[id[fx][fy]]==-1||i==d) continue;
 59         edge_add(id[sx][sy]+d,id[sx][sy]+i,dis[id[fx][fy]]);
 60     }    
 61     edge_add(id[sx][sy]+d,id[ex][ey]+(d+2)%4,1);
 62 }
 63 void bfsS(int ex,int ey,int sx,int sy)
 64 {
 65     queue<node>q;
 66     memset(dis,-1,sizeof(dis));
 67     q.push(ins(ex,ey)),dis[id[ex][ey]]=0;
 68     int x,y,fx,fy;
 69     while(!q.empty())
 70     {
 71         node k=q.front();q.pop();
 72         x=k.x,y=k.y;
 73         for(int i=0;i<4;i++)
 74         {
 75             fx=x+xx[i],fy=y+yy[i];
 76             if(!check(fx,fy)||dis[id[fx][fy]]!=-1||(fx==sx&&fy==sy)) continue;
 77             dis[id[fx][fy]]=dis[id[x][y]]+1;
 78             q.push(ins(fx,fy));
 79         }
 80     }
 81 }
 82 void build_edge()
 83 {
 84     int ct=1;
 85     for(int i=1;i<=n;i++)
 86         for(int j=1;j<=m;j++)
 87         {
 88             if(ok[i][j]) id[i][j]=ct,ct+=4;
 89         } 
 90     for(int i=1;i<=n;i++)
 91         for(int j=1;j<=m;j++)
 92         {
 93             if(!check(i,j)) continue;
 94             if(check(i-1,j)) bfs(i-1,j,i,j,0);
 95             if(check(i,j+1)) bfs(i,j+1,i,j,1);
 96             if(check(i+1,j)) bfs(i+1,j,i,j,2);
 97             if(check(i,j-1)) bfs(i,j-1,i,j,3);
 98         } 
 99 }
100 void spfa(int S)
101 {
102     queue<int>q;
103     memset(dis,0x3f,sizeof(dis));
104     q.push(S),dis[S]=0,inq[S]=1;
105     while(!q.empty())
106     {
107         int u=q.front();q.pop();
108         for(int j=head[u];j!=-1;j=edge[j].nxt)
109         {
110             int v=edge[j].to;
111             if(dis[v]>dis[u]+edge[j].val)
112             {
113                 dis[v]=dis[u]+edge[j].val;
114                 if(!inq[v]) q.push(v),inq[v]=1;
115             }
116         }
117         inq[u]=0;
118     }
119 }
120 
121 int solve(int ex,int ey,int sx,int sy,int tx,int ty)
122 {
123     bfsS(ex,ey,sx,sy);
124     if(sx==tx&&sy==ty) return 0;
125     for(int i=0;i<4;i++) st[i]=dis[id[sx+xx[i]][sy+yy[i]]];
126     int fx,fy,ans=inf;
127     for(int i=0;i<4;i++)
128     {
129         fx=sx+xx[i],fy=sy+yy[i];
130         if(!check(fx,fy)||st[i]==-1) continue;
131         spfa(id[sx][sy]+i);
132         for(int j=0;j<4;j++)
133         {
134             if(!check(tx+xx[j],ty+yy[j])||dis[id[tx][ty]+j]==-1) continue;
135             ans=min(ans,st[i]+dis[id[tx][ty]+j]);
136         } 
137     }
138     if(ans>=inf) return -1;
139     else return ans;
140 }
141 
142 int main()
143 {
144     freopen("aa.in","r",stdin);
145     scanf("%d%d%d",&n,&m,&q);
146     for(int i=1;i<=n;i++)
147         for(int j=1;j<=m;j++)
148             scanf("%d",&ok[i][j]);
149     memset(head,-1,sizeof(head));
150     build_edge();
151     int ex,ey,sx,sy,tx,ty;
152     while(q--)
153     {
154         scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty);
155         printf("%d\n",solve(ex,ey,sx,sy,tx,ty));
156     }
157     return 0;
158 }

 

---恢复内容开始---

题目大意:类似于华容道游戏,但所有棋子都是1NOIP2013 华容道 (棋盘建图+spfa最短路)1大小的,棋盘上仅有一个空格,其它位置填满了棋子,有些棋子是固定的不能被移动,每个格子内只能有一个棋子,棋子只能移动到相邻的空格上,每移动任意棋子一次视为一次操作,求让指定棋子移动到指定位置的最小操作数

据说爆搜能拿70pts....

观察爆搜为什么会T,主要是因为搜出了许多无用的状态

考虑优化这个过程,空格在指定棋子的上下左右分别记为一种状态,相当于一个位置记录了4个状态

为了方便转移,直接把每个格子的四个状态记成连续的,这样方便转移

每种状态,它能转移到其它状态的情况分为两种:

<1>指定格子的某个方向有空格,转移到同一个格子的另一个方向有空格,指定格子上的棋子的位置不动

这种情况,我们对于每个格子的四个方向分别bfs即可,因为除了空格子,其它位置都被填满了,所以空格子在被填满的棋盘里移动,和棋子在空棋盘里的移动方式是一样的(貌似是一句废话但我仍然思考了很久...)

<2>指定棋子朝着这个状态指向的空格移动

这种情况,显然操作次数为1,转移的状态呢,则是从 当前格子的指向 转移到 目标格子的反方向 (就是那个(d+2)%4)

虽然有500次询问,但图都是一样的,所以建一次图就行

那么,如果一开始空格子不在指定棋子边上呢?

我们把空格子移动到指定棋子的四个方向就行了,注意不要让空格子移动到指定棋子的格子上

再分别跑一次SPFA最短路即可

总结:之前还有一道棋盘建图题(荷叶塘),但那道题建图更简单更好想,思路都是先bfs建边,然后跑最短路

注意特判移动次数为0的情况!

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define inf 0x3f3f3f3f
#define N 35
#define maxn 5000
#define mod 1000000007
#define ll long long 
using namespace std;

int n,m,q,cte;
int ok[N][N],id[N][N],head[maxn],dis[maxn],inq[maxn],st[4];
int xx[]={-1,0,1,0};
int yy[]={0,1,0,-1};
struct EDGE{
    int to,nxt,val;
}edge[maxn*500];
struct node{
    int x,y;
};
node ins(int s1,int s2) {node k;k.x=s1;k.y=s2;return k;}
bool check(int x,int y)
{
    if(x<1||y<1||x>n||y>m||!ok[x][y]) return false;
    else return true;
}
void edge_add(int u,int v,int w)
{
    cte++;
    edge[cte].to = v;
    edge[cte].nxt=head[u];
    edge[cte].val= w;
    head[u]=cte;
}
void bfs(int ex,int ey,int sx,int sy,int d)
{
    queue<node>q;
    memset(dis,-1,sizeof(dis));
    dis[id[ex][ey]]=0,dis[id[sx][sy]]=1;
    q.push(ins(ex,ey));
    int x,y,fx,fy;
    while(!q.empty())
    {
        node k=q.front();q.pop();
        x=k.x,y=k.y;
        for(int i=0;i<4;i++)
        {
            fx=x+xx[i],fy=y+yy[i];
            if(!check(fx,fy)||dis[id[fx][fy]]!=-1) continue;
            dis[id[fx][fy]]=dis[id[x][y]]+1;
            q.push(ins(fx,fy));
        }
    }
    for(int i=0;i<4;i++)
    {
        fx=sx+xx[i],fy=sy+yy[i];
        if(!check(fx,fy)||dis[id[fx][fy]]==-1||i==d) continue;
        edge_add(id[sx][sy]+d,id[sx][sy]+i,dis[id[fx][fy]]);
    }    
    edge_add(id[sx][sy]+d,id[ex][ey]+(d+2)%4,1);
}
void bfsS(int ex,int ey,int sx,int sy)
{
    queue<node>q;
    memset(dis,-1,sizeof(dis));
    q.push(ins(ex,ey)),dis[id[ex][ey]]=0;
    int x,y,fx,fy;
    while(!q.empty())
    {
        node k=q.front();q.pop();
        x=k.x,y=k.y;
        for(int i=0;i<4;i++)
        {
            fx=x+xx[i],fy=y+yy[i];
            if(!check(fx,fy)||dis[id[fx][fy]]!=-1||(fx==sx&&fy==sy)) continue;
            dis[id[fx][fy]]=dis[id[x][y]]+1;
            q.push(ins(fx,fy));
        }
    }
}
void build_edge()
{
    int ct=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(ok[i][j]) id[i][j]=ct,ct+=4;
        } 
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(!check(i,j)) continue;
            if(check(i-1,j)) bfs(i-1,j,i,j,0);
            if(check(i,j+1)) bfs(i,j+1,i,j,1);
            if(check(i+1,j)) bfs(i+1,j,i,j,2);
            if(check(i,j-1)) bfs(i,j-1,i,j,3);
        } 
}
void spfa(int S)
{
    queue<int>q;
    memset(dis,0x3f,sizeof(dis));
    q.push(S),dis[S]=0,inq[S]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int j=head[u];j!=-1;j=edge[j].nxt)
        {
            int v=edge[j].to;
            if(dis[v]>dis[u]+edge[j].val)
            {
                dis[v]=dis[u]+edge[j].val;
                if(!inq[v]) q.push(v),inq[v]=1;
            }
        }
        inq[u]=0;
    }
}

int solve(int ex,int ey,int sx,int sy,int tx,int ty)
{
    bfsS(ex,ey,sx,sy);
    if(sx==tx&&sy==ty) return 0;
    for(int i=0;i<4;i++) st[i]=dis[id[sx+xx[i]][sy+yy[i]]];
    int fx,fy,ans=inf;
    for(int i=0;i<4;i++)
    {
        fx=sx+xx[i],fy=sy+yy[i];
        if(!check(fx,fy)||st[i]==-1) continue;
        spfa(id[sx][sy]+i);
        for(int j=0;j<4;j++)
        {
            if(!check(tx+xx[j],ty+yy[j])||dis[id[tx][ty]+j]==-1) continue;
            ans=min(ans,st[i]+dis[id[tx][ty]+j]);
        } 
    }
    if(ans>=inf) return -1;
    else return ans;
}

int main()
{
    freopen("aa.in","r",stdin);
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&ok[i][j]);
    memset(head,-1,sizeof(head));
    build_edge();
    int ex,ey,sx,sy,tx,ty;
    while(q--)
    {
        scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty);
        printf("%d\n",solve(ex,ey,sx,sy,tx,ty));
    }
    return 0;
}

 

---恢复内容结束---