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 }
---恢复内容开始---
题目大意：类似于华容道游戏，但所有棋子都是1
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; }
---恢复内容结束---