题目: https://www.luogu.org/problemnew/show/P1979
感到无从下手. 但不妨用 dp 的角度来看. 因为空格只有在指定棋子的旁边才有用, 所以状态记成制定棋子的位置与空格在自己的哪侧.
转移有两种: 与空格交换位置 或 让空格换一个方向. 为了第二个转移, 需要预处理, bfs 出指定棋子在 (x,y) 时从它的哪边走到哪边的最短路.
dp 的转移可以套到最短路里做. 一开始需要让空格来到指定棋子的四个方向 (bfs). 然后多源最短路或者做 4 遍最短路.
别忘了优先队列自然的就是从大到小排列的!!!
自己的写法需要特判走 0 步的情况.
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<queue>
- using namespace std;
- const int N=35,K=5,M=N*N,INF=0x3f3f3f3f-100;
- int n,m,Q,f[N][N][K][K],dis[N][N],dp[N][N][K];
- int he,tl,xx[K]={-1,0,0,1},yy[K]={0,-1,1,0};
- int ex,ey,sx,sy,Tx,Ty,ans,tmp;
- bool b[N][N],vis[N][N][K];
- struct Node{
- int x,y,p,dis;
- Node(int x=0,int y=0,int a=0,int d=0):x(x),y(y),p(a),dis(d) {}
- bool operator<(const Node &b) const
- {return dis>b.dis;}//>!!!
- }q[M];
- priority_queue<Node> qu;
- void bfs(int x1,int y1,int x2,int y2)
- {
- he=tl=0; int tx,ty;
- q[++tl]=Node(x1,y1,0,0);
- memset(dis,0x3f,sizeof dis);
- dis[x1][y1]=0;
- while(he<tl)
- {
- Node k=q[++he];
- for(int i=0;i<=3;i++)
- {
- tx=k.x+xx[i]; ty=k.y+yy[i];
- if(!b[tx][ty])continue;
- if(dis[tx][ty]>INF)
- {
- dis[tx][ty]=dis[k.x][k.y]+1;
- q[++tl]=Node(tx,ty,0,0);
- if(tx==x2&&ty==y2)return;
- }
- }
- }
- }
- void init()
- {
- memset(f,0x3f,sizeof f);
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m;j++) if(b[i][j])
- for(int p0=0;p0<=3;p0++)
- for(int p1=p0+1,x1,y1,x2,y2;p1<=3;p1++)
- {
- x1=i+xx[p0]; y1=j+yy[p0];
- x2=i+xx[p1]; y2=j+yy[p1];
- if(!b[x1][y1]||!b[x2][y2]) continue;
- b[i][j]=0;
- bfs(x1,y1,x2,y2);
- f[i][j][p0][p1]=f[i][j][p1][p0]
- =dis[x2][y2];
- b[i][j]=1;
- }
- }
- void solve(int yp)
- {
- while(qu.size())qu.pop();
- qu.push(Node(sx,sy,yp,0));
- memset(dp,0x3f,sizeof dp); dp[sx][sy][yp]=0;//
- memset(vis,0,sizeof vis);
- while(qu.size())
- {
- Node k=qu.top(); qu.pop();
- if(vis[k.x][k.y][k.p])continue;
- vis[k.x][k.y][k.p]=1;
- if(k.x==Tx&&k.y==Ty)return;
- int tp=3-k.p,tx=k.x+xx[k.p],ty=k.y+yy[k.p];
- if(dp[tx][ty][tp]>dp[k.x][k.y][k.p]+1)
- {
- dp[tx][ty][tp]=dp[k.x][k.y][k.p]+1;
- qu.push(Node(tx,ty,tp,dp[tx][ty][tp]));
- }
- tx=k.x; ty=k.y; tp=k.p;
- for(int i=0;i<=3;i++)
- {
- if(i==tp)continue;
- if(f[tx][ty][tp][i]<INF&&
- dp[tx][ty][i]>dp[tx][ty][tp]+f[tx][ty][tp][i])
- {
- dp[tx][ty][i]=dp[tx][ty][tp]+f[tx][ty][tp][i];
- qu.push(Node(tx,ty,i,dp[tx][ty][i]));
- }
- }
- }
- }
- int main()
- {
- scanf("%d%d%d",&n,&m,&Q);
- for(int i=1;i<=n;i++)
- for(int j=1,d;j<=m;j++)
- scanf("%d",&d),b[i][j]=d;
- init();
- he=tl=0;
- while(Q--)
- {
- scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&Tx,&Ty);
- if(sx==Tx&&sy==Ty)
- {
- printf("0\n"); continue;
- }
- ans=INF+5;
- for(int i=0,tx,ty;i<=3;i++)
- {
- tx=sx+xx[i]; ty=sy+yy[i];
- if(!b[tx][ty])continue;
- b[sx][sy]=0;
- bfs(ex,ey,tx,ty);
- b[sx][sy]=1;
- tmp=dis[tx][ty];
- if(tmp>INF)continue;
- solve(i);
- ans=min(ans,tmp+min(min(dp[Tx][Ty][0],dp[Tx][Ty][1]),
- min(dp[Tx][Ty][2],dp[Tx][Ty][3])));
- }
- printf("%d\n",ans>INF?-1:ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2781403.html