正題

luogu 7473

---

題目大意

給出一個正方形區(qū)域，中間有一些障礙
現(xiàn)在有兩個球，每次操作可以使兩個球同時向一個方向移動，直到遇到障礙或邊界
現(xiàn)在問你讓兩個球到同一個位置最少要多少步

---

解題思路

對于每次操作，球只有可能停在障礙四周的格子內(nèi)（邊界視為障礙），把這些格子記錄下來

然后暴力枚舉它們之間的連邊，這里倒著連邊從最終狀態(tài)轉(zhuǎn)移到初始狀態(tài)

對于每個這樣的點(diǎn)x，建立狀態(tài)(x,x)，兩個值分別為當(dāng)前狀態(tài)兩個點(diǎn)的位置，那么bfs即可

代碼

#include<cstdio> #include<queue> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 260 using namespace std; int n, m, q, x, y, w, g, xx, yy, tot, p[N][N], v[N][N], f[N*20][N*20], head[N*20][4], to[N][N][4]; struct rec {int to, next; }a[N*20*4]; struct node {int x, y; }; queue<node>d; bool check(int x, int y) {return p[x + 1][y] || p[x - 1][y] || p[x][y + 1] || p[x][y - 1]; } void add(int x, int y, int z) {a[++tot].to = y;a[tot].next = head[x][z];head[x][z] = tot; } int main() {scanf("%d%d%d", &n, &m, &q);for (int i = 1; i <= m; ++i){scanf("%d%d", &x, &y);p[x][y] = 1;}for (int i = 1; i <= n; ++i)p[i][0] = p[i][n + 1] = p[0][i] = p[n + 1][i] = 1;for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)if (!p[i][j] && check(i, j))v[i][j] = ++w;//記下特殊點(diǎn)for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j){to[i][j][0] = p[i][j - 1] ? v[i][j] : to[i][j - 1][0];//查詢往各個方向走會到哪個點(diǎn)to[i][j][1] = p[i - 1][j] ? v[i][j] : to[i - 1][j][1];}for (int i = n; i > 0; --i)for (int j = n; j > 0; --j){to[i][j][2] = p[i][j + 1] ? v[i][j] : to[i][j + 1][2];to[i][j][3] = p[i + 1][j] ? v[i][j] : to[i + 1][j][3];}for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)if (v[i][j])for (int k = 0; k < 4; ++k)add(to[i][j][k], v[i][j], k);//連反邊memset(f, 127/3, sizeof(f));for (int i = 1; i <= w; ++i){d.push((node){i, i});//最終狀態(tài)f[i][i] = 0;}while(!d.empty()){node h = d.front();d.pop();for (int k = 0; k < 4; ++k)//bfsfor (int i = head[h.x][k]; i; i = a[i].next)for (int j = head[h.y][k]; j; j = a[j].next)if (f[a[i].to][a[j].to] > 1e8){f[a[i].to][a[j].to] = f[h.x][h.y] + 1;d.push((node){a[i].to, a[j].to});}}while(q--){scanf("%d%d%d%d", &x, &y, &xx, &yy);g = x == xx && y == yy ? 0 : 1e8;for (int k = 0; k < 4; ++k)g = min(g, f[to[x][y][k]][to[xx][yy][k]] + 1);//往其中一個方向走，然后就可以直接使用bfs得出的結(jié)果if (g < 1e8) printf("%d\n", g);else puts("-1");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的【bfs】重力球（luogu 7473/NOI Online 2021 普及组 T3）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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