昆明建设路租房信息昆明租房网站,柘城网站建设,建立网站地图,aspnet网站开发 视频题目传送门 题意#xff1a;给出一个$N \times M$的棋盘#xff0c;棋盘上有一些块可以移动#xff0c;有一些块无法移动。$Q$次询问#xff0c;每一次询问给出三个块$a,b,c$#xff0c;将$a$块变为空格#xff0c;空格旁边可移动的块可以与空格交换位置。问每一次询问中…题目传送门 题意给出一个$N \times M$的棋盘棋盘上有一些块可以移动有一些块无法移动。$Q$次询问每一次询问给出三个块$a,b,c$将$a$块变为空格空格旁边可移动的块可以与空格交换位置。问每一次询问中最小的将$b$块移动到$c$块最开始位置上的移动次数。$N , M \leq 30 , Q \leq 500$ 我觉得我在$NOIP$考场上绝对会直接打暴力qwq 我们能够发现空格必须要在需要移动的格子的四周而且不移动需要移动的格子才能发挥效果。所以当空格在需要移动的格子旁边的时候只有两种情况①将需要移动的格子与空格交换位置②将空格移动到需要移动的格子的另一侧。所以我们预处理$f_{i,j,k,l}$表示将空格从格子$i,j$的方向$k$移动到方向$l$且不移动$(i,j)$的最少步数可以通过$bfs$实现复杂度$O(16N^2M^2)$ 接下来就是一个类似于最短路的问题了。然而最开始空格与需要移动的格子不相邻所以我们在每一次询问的时候再一次$bfs$计算现在空格的位置到达需要移动的格子四周且不移动需要移动的格子的最少移动次数然后跑$SPFA$即可。因为图很小卡不了$SPFA$。 1 #includebits/stdc.h2 using namespace std;3 4 inline int read(){5 int a 0;6 char c getchar();7 while(!isdigit(c))8 c getchar();9 while(isdigit(c)){10 a (a 3) (a 1) (c ^ 0);11 c getchar();12 }13 return a;14 }15 16 const int dir[4][2] {0,1,1,0,-1,0,0,-1};17 int f[31][31][4][4] , dis[31][31][4] , t[31][31] , N , M , Q;18 bool canbe[32][32] , inq[31][31][4];19 struct be{20 int x , y , dir;21 }now;22 23 queue pair int , int q;24 queue be q1;25 26 inline int SPFA(int aX , int aY , int bX , int bY , int cX , int cY){27 while(!q.empty())28 q.pop();29 if(!canbe[aX][aY] || !canbe[bX][bY])30 return 0x3f3f3f3f;31 memset(t , 0x3f , sizeof(t));32 t[aX][aY] 0;33 q.push(make_pair(aX , aY));34 while(!q.empty()){35 pair int , int r q.front();36 q.pop();37 if(r.first bX r.second bY)38 return t[bX][bY];39 for(int i 0 ; i 4 ; i)40 if(r.first dir[i][0] ! cX || r.second dir[i][1] ! cY)41 if(canbe[r.first dir[i][0]][r.second dir[i][1]])42 if(t[r.first dir[i][0]][r.second dir[i][1]] t[r.first][r.second] 1){43 t[r.first dir[i][0]][r.second dir[i][1]] t[r.first][r.second] 1;44 q.push(make_pair(r.first dir[i][0] , r.second dir[i][1]));45 }46 }47 return 0x3f3f3f3f;48 }49 50 inline void bfs(int sX , int sY , int tX , int tY){51 for(int i 0 ; i 4 ; i)52 if(dis[sX][sY][i] ! 0x3f3f3f3f){53 inq[sX][sY][i] 1;54 q1.push((be){sX , sY , i});55 }56 while(!q1.empty()){57 now q1.front();58 inq[now.x][now.y][now.dir] 0;59 q1.pop();60 if(now.x tX now.y tY)61 continue;62 for(int i 0 ; i 4 ; i)63 if(now.dir ! i){64 int N dis[now.x][now.y][now.dir] f[now.x][now.y][now.dir][i];65 if(dis[now.x][now.y][i] N){66 dis[now.x][now.y][i] N;67 if(!inq[now.x][now.y][i]){68 inq[now.x][now.y][i] 1;69 q1.push((be){now.x , now.y , i});70 }71 }72 }73 if(dis[now.x dir[now.dir][0]][now.y dir[now.dir][1]][3 - now.dir] dis[now.x][now.y][now.dir] 1){74 dis[now.x dir[now.dir][0]][now.y dir[now.dir][1]][3 - now.dir] dis[now.x][now.y][now.dir] 1;75 if(!inq[now.x dir[now.dir][0]][now.y dir[now.dir][1]][3 - now.dir]){76 inq[now.x dir[now.dir][0]][now.y dir[now.dir][1]][3 - now.dir] 1;77 q1.push((be){now.x dir[now.dir][0] , now.y dir[now.dir][1] , 3 - now.dir});78 }79 }80 }81 }82 83 int main(){84 N read();85 M read();86 Q read();87 for(int i 1 ; i N ; i)88 for(int j 1 ; j M ; j)89 canbe[i][j] read();90 memset(f , 0x3f , sizeof(f));91 for(int i 1 ; i N ; i)92 for(int j 1 ; j M ; j)93 if(canbe[i][j])94 for(int m 0 ; m 3 ; m)95 for(int n 0 ; n 3 ; n)96 f[i][j][m][n] SPFA(i dir[m][0] , j dir[m][1] , i dir[n][0] , j dir[n][1] , i , j);97 while(Q--){98 int a read() , b read() , c read() , d read() , e read() , f read();99 if(c e d f){
100 printf(0\n);
101 continue;
102 }
103 memset(dis , 0x3f , sizeof(dis));
104 for(int i 0 ; i 4 ; i)
105 dis[c][d][i] SPFA(a , b , c dir[i][0] , d dir[i][1] , c , d);
106 bfs(c , d , e , f);
107 int ans 0x3f3f3f3f;
108 for(int i 0 ; i 4 ; i)
109 ans min(ans , dis[e][f][i]);
110 printf(%d\n , ans 0x3f3f3f3f ? -1 : ans);
111 }
112 return 0;
113 } 转载于:https://www.cnblogs.com/Itst/p/9782108.html