ABC-400-D - Takahashi the Wall Breaker（BFS双段队列优化or堆优化） · znzryb
## 思路讲解
双段队列优化，让cnt比较低的先走，这样子保证可以被比较好的剪枝
也可以使用堆优化，比双段队列deque稍慢，但也还行。
## AC代码
[https://atcoder.jp/contests/abc400/submissions/64555057](https://atcoder.jp/contests/abc400/submissions/64555057)
::: 双段队列优化源代码
```cpp
// Problem: D - Takahashi the Wall Breaker
// Contest: AtCoder - AtCoder Beginner Contest 400
// URL: https://atcoder.jp/contests/abc400/tasks/abc400_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h> // Includes <deque>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128; // Consider if __int128 is really needed, ll might suffice.
typedef pair<ll,ll> pll;
typedef array<ll,3> arr; // {cost, row, col}
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e3)+10;
// Using long long INF is good practice for large grids or costs
constexpr ll INF=static_cast<ll>(4e18); // Adjusted INF to avoid overflow if summing costs many times, though 5e18 is likely fine too.
ll N,M,T,A,B,C,D;
char maze[MAXN][MAXN];
ll vis[MAXN][MAXN]; // Stores minimum cost (spells) to reach cell (i, j)
// Directions for normal moves (cost 0)
ll dx[4]={1,0,-1,0};
ll dy[4]={0,-1,0,1};
// Relative coordinates for magic moves (cost 1)
// This covers adjacent cells (dist 1) and jumps (dist 2) in the 5x5 area
// A more explicit approach with separate loops for adjacent and jumps is also fine.
// Let's stick to the explicit approach for clarity, matching the original intent better.
ll magic_dx[] = {1, 0, -1, 0, 2, 0, -2, 0}; // Adjacent + Jumps X
ll magic_dy[] = {0, -1, 0, 1, 0, 2, 0, -2}; // Adjacent + Jumps Y
inline void solve(){
cin>>N>>M;
FOR(i,1,N){
FOR(j,1,M){
cin>>maze[i][j];
vis[i][j]=INF; // Initialize costs to infinity
}
}
cin>>A>>B>>C>>D;
deque<arr> q; // Use deque for 0-1 BFS
vis[A][B]=0;
q.push_front({0,A,B}); // Start with 0 cost, push to front
while(!q.empty()){
arr current = q.front();
q.pop_front();
ll cnt=current[0];
ll x=current[1];
ll y=current[2];
// Optimization: If we found a shorter path to (x, y) already, skip processing this one.
if (cnt > vis[x][y]) {
continue;
}
// --- Explore Cost 0 Moves (Normal adjacent moves to '.') ---
FOR(i,0,3){
ll fx=x+dx[i];
ll fy=y+dy[i];
// Check boundaries
if(fx<1 || fx>N || fy<1 || fy>M) continue;
// Can only move normally into empty cells
if(maze[fx][fy]=='#') continue;
// If we found a path with the same or lower cost (cnt)
if(vis[fx][fy] > cnt) { // Use '>' because cost is the same (cnt)
vis[fx][fy]=cnt;
q.push_front({cnt, fx, fy}); // Push to FRONT for cost 0
}
}
// --- Explore Cost 1 Moves (Magic: Adjacent or Jump) ---
ll next_cost = cnt + 1;
// Iterate through all 8 possible magic moves (4 adjacent, 4 jumps)
FOR(i,0,7){ // Use the combined magic_dx/dy arrays
ll fx=x+magic_dx[i];
ll fy=y+magic_dy[i];
// Check boundaries
if(fx<1 || fx>N || fy<1 || fy>M) continue;
// Can use magic on '#' or '.'
// If we found a path with lower cost (next_cost)
if(vis[fx][fy] > next_cost){
vis[fx][fy]=next_cost;
q.push_back({next_cost, fx, fy}); // Push to BACK for cost 1
}
}
}
// Output result
if (vis[C][D] == INF) {
// Depending on problem statement, output -1 or the INF value if unreachable
// Sticking to original behavior: print the value in vis[C][D]
cout << -1 << "\n"; // Common practice if unreachable needs specific output
} else {
cout<<vis[C][D]<<"\n";
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// cin>>T; // Uncomment if there are multiple test cases
// while(T--){
// solve();
// }
solve(); // Call solve once if only one test case
return 0;
}
```
:::
[https://atcoder.jp/contests/abc400/submissions/64575744](https://atcoder.jp/contests/abc400/submissions/64575744)
::: 堆优化源代码
```cpp
// Problem: D - Takahashi the Wall Breaker
// Contest: AtCoder - AtCoder Beginner Contest 400
// URL: https://atcoder.jp/contests/abc400/tasks/abc400_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e3)+10,INF=static_cast<ll>(5e18)+3;
ll N,M,T,A,B,C,D;
char maze[MAXN][MAXN];
ll vis[MAXN][MAXN];
ll dx[4]={1,0,-1,0};
ll dy[4]={0,-1,0,1};
ll kx[4]={2,0,-2,0};
ll ky[4]={0,-2,0,2};
struct cmp{
bool operator()(arr a,arr b){
return a[0]>b[0];
}
};
inline void solve(){
cin>>N>>M;
FOR(i,1,N){
FOR(j,1,M){
cin>>maze[i][j];
vis[i][j]=INF;
}
}
cin>>A>>B>>C>>D;
priority_queue<arr,vector<arr>,cmp> q;
q.push({0,A,B});
vis[A][B]=0;
while(!q.empty()){
ll cnt=q.top()[0],x=q.top()[1],y=q.top()[2];
q.pop();
FOR(i,0,3){
ll fx=x+dx[i],fy=y+dy[i];
if(fx<1 || fx>N) continue;
if(fy<1 || fy>M) continue;
if(vis[fx][fy]<=cnt) continue;
if(maze[fx][fy]=='#') continue;
vis[fx][fy]=cnt;
q.push({cnt,fx,fy});
}
FOR(i,0,3){
ll fx=x+dx[i],fy=y+dy[i];
if(fx<1 || fx>N) continue;
if(fy<1 || fy>M) continue;
if(vis[fx][fy]<=cnt+1) continue;
vis[fx][fy]=cnt+1;
q.push({cnt+1,fx,fy});
}
FOR(i,0,3){
ll fx=x+kx[i],fy=y+ky[i];
if(fx<1 || fx>N) continue;
if(fy<1 || fy>M) continue;
if(vis[fx][fy]<=cnt+1) continue;
vis[fx][fy]=cnt+1;
q.push({cnt+1,fx,fy});
}
}
cout<<vis[C][D]<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// cin>>T;
// while(T--){
// solve();
// }
solve();
return 0;
}
/*
AC
https://atcoder.jp/contests/abc400/submissions/64575744
*/
```
:::
## 心路历程（WA，TLE，MLE……）