ABC-400-D - Takahashi the Wall Breaker（BFS双段队列优化or堆优化）

思路讲解

双段队列优化，让cnt比较低的先走，这样子保证可以被比较好的剪枝

也可以使用堆优化，比双段队列deque稍慢，但也还行。

AC代码

https://atcoder.jp/contests/abc400/submissions/64555057

双段队列优化源代码

// 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

堆优化源代码

// 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……）