題目傳送門

題意：給出一個(gè)$N \times M$的棋盤，棋盤上有一些塊可以移動(dòng)，有一些塊無(wú)法移動(dòng)。$Q$次詢問(wèn)，每一次詢問(wèn)給出三個(gè)塊$a,b,c$，將$a$塊變?yōu)榭崭?#xff0c;空格旁邊可移動(dòng)的塊可以與空格交換位置。問(wèn)每一次詢問(wèn)中最小的將$b$塊移動(dòng)到$c$塊最開(kāi)始位置上的移動(dòng)次數(shù)。$N , M \leq 30 , Q \leq 500$

---

我覺(jué)得我在$NOIP$考場(chǎng)上絕對(duì)會(huì)直接打暴力qwq

我們能夠發(fā)現(xiàn)空格必須要在需要移動(dòng)的格子的四周，而且不移動(dòng)需要移動(dòng)的格子，才能發(fā)揮效果。所以當(dāng)空格在需要移動(dòng)的格子旁邊的時(shí)候，只有兩種情況：①將需要移動(dòng)的格子與空格交換位置；②將空格移動(dòng)到需要移動(dòng)的格子的另一側(cè)。所以我們預(yù)處理：$f_{i,j,k,l}$表示將空格從格子$i,j$的方向$k$移動(dòng)到方向$l$且不移動(dòng)$(i,j)$的最少步數(shù)，可以通過(guò)$bfs$實(shí)現(xiàn)，復(fù)雜度$O(16N^2M^2)$

接下來(lái)就是一個(gè)類似于最短路的問(wèn)題了。然而最開(kāi)始空格與需要移動(dòng)的格子不相鄰，所以我們?cè)诿恳淮卧儐?wèn)的時(shí)候，再一次$bfs$計(jì)算現(xiàn)在空格的位置到達(dá)需要移動(dòng)的格子四周且不移動(dòng)需要移動(dòng)的格子的最少移動(dòng)次數(shù)，然后跑$SPFA$即可。因?yàn)閳D很小，卡不了$SPFA$。

1 #include<bits/stdc++.h> 2 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 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Itst/p/9782108.html

總結(jié)

以上是生活随笔為你收集整理的Luogu1979 NOIP2013D2T3 华容道 搜索、最短路的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。