1 #include2 #include 3 #include 4 #include 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 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 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 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 }
---恢复内容开始---
题目大意：类似于华容道游戏，但所有棋子都是11大小的，棋盘上仅有一个空格，其它位置填满了棋子，有些棋子是固定的不能被移动，每个格子内只能有一个棋子，棋子只能移动到相邻的空格上，每移动任意棋子一次视为一次操作，求让指定棋子移动到指定位置的最小操作数
据说爆搜能拿70pts....
观察爆搜为什么会T，主要是因为搜出了许多无用的状态
考虑优化这个过程，空格在指定棋子的上下左右分别记为一种状态，相当于一个位置记录了4个状态
为了方便转移，直接把每个格子的四个状态记成连续的，这样方便转移
每种状态，它能转移到其它状态的情况分为两种：
<1>指定格子的某个方向有空格，转移到同一个格子的另一个方向有空格，指定格子上的棋子的位置不动
这种情况，我们对于每个格子的四个方向分别bfs即可，因为除了空格子，其它位置都被填满了，所以空格子在被填满的棋盘里移动，和棋子在空棋盘里的移动方式是一样的（貌似是一句废话但我仍然思考了很久...）
<2>指定棋子朝着这个状态指向的空格移动
这种情况，显然操作次数为1，转移的状态呢，则是从 当前格子的指向 转移到 目标格子的反方向 (就是那个(d+2)%4)
虽然有500次询问，但图都是一样的，所以建一次图就行
那么，如果一开始空格子不在指定棋子边上呢？
我们把空格子移动到指定棋子的四个方向就行了，注意不要让空格子移动到指定棋子的格子上
再分别跑一次SPFA最短路即可
总结：之前还有一道棋盘建图题（荷叶塘），但那道题建图更简单更好想，思路都是先bfs建边，然后跑最短路
注意特判移动次数为0的情况！
#include#include #include #include #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 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 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 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;}
---恢复内容结束---