F题求助

求个hack数据（dist没加第三维方向只能过40%，加了就AC了），想不到

不加方向

#include<bits/stdc++.h>

#define lc p << 1
#define rc p << 1 | 1
#define lowbit(x) x & -x
#define inv(x) qmi(x, P - 2)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
const int N = 2e5 + 10;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f;
const double PI = 3.141592653;
const ll P = 1e9 + 7;

int T = 1;
ll qmi(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % P;
        b >>= 1;
        a = a * a % P;
    }
    return res;
}
ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}
void print_lll(lll x){
    if(!x) cout << 0 << '\n';
    else{
        vector<int> nums;
        while(x) nums.push_back(x % 10), x /= 10;
        for(int i = 0; i < nums.size(); i ++) cout << nums[i];
    }
}

void print(vector<ll> a, int n){
    for(int i = 0; i < n; i ++){
        if(i < n - 1) cout << a[i] << ' ';
        else cout << a[i];
    }
}

void solve(){
    int n, m, h;
    cin >> n >> m >> h;
    
    vector<vector<char>> g(n + 10, vector<char>(m + 10));
    int stx, sty, edx, edy;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++){
            cin >> g[i][j];
            if(g[i][j] == '*') stx = i, sty = j;
            if(g[i][j] == '%') edx = i, edy = j;
        }
    struct node{
        int x, y, op, d;
        bool operator<(const node&b) const{
            return d > b.d;
        }
    };
    auto check = [&](int x, int y) -> int{
        return (x >= 1 && y >= 1 && x <= n && y <= m);  
    };
    
    //这里注意：3个方向，dist只开2维会把不同方向的dist覆盖掉
    vector<vector<int>> dist(n + 10, vector<int>(m + 10, inf));
    priority_queue<node> heap;
    heap.push({stx, sty, 0, 0});
    dist[stx][sty] = 0;
    while(heap.size()){
        node t = heap.top();
        heap.pop();
        int x = t.x, y = t.y, op = t.op, d = t.d;
        int ly = y - 1, ry = y + 1;            
        int nex = x + 1, ney = y;
        if(!check(nex, ney)) continue;
        if(!op){
            if(g[nex][ney] == '#'){
                if(check(x, ly) && g[x][ly] != '#' && dist[x][ly] > d + 1){
                    dist[x][ly] = d + 1;
                    heap.push({x, ly, 1, dist[x][ly]});
                }
                if(check(x, ry) && g[x][ry] != '#' && dist[x][ry] > d + 1){
                    dist[x][ry] = d + 1;
                    heap.push({x, ry, 2, dist[x][ry]});
                }
                if(dist[nex][ney] > d + h + 1){
                    dist[nex][ney] = d + h + 1;
                    heap.push({nex, ney, 0, dist[nex][ney]});
                }
            }
            else{
                if(dist[x + 1][y] > d + 1){
                    dist[x + 1][y] = d + 1;
                    heap.push({x + 1, y, 0, dist[x + 1][y]});
                }
            }
        }
        else if(op == 1){
            if(g[x + 1][y] == '#'){
                if(check(x, ly) && g[x][ly] != '#' && dist[x][ly] > d + 1){
                    dist[x][ly] = dist[x][y] + 1;
                    heap.push({x, ly, 1, dist[x][ly]});
                }
            }
            else{
                if(dist[x + 1][y] > d + 1){
                    dist[x + 1][y] = d + 1;
                    heap.push({x + 1, y, 0, dist[x + 1][y]});
                }
            }
        }
        else{
            if(check(x + 1, y)){
                if(g[x + 1][y] == '#'){
                    if(check(x, ry) && g[x][ry] != '#' && dist[x][ry] > d + 1){
                        dist[x][ry] = d + 1;
                        heap.push({x, ry, 2, dist[x][ry]});
                    }
                }
                else{
                    if(dist[x + 1][y] > d + 1){
                        dist[x + 1][y] = d + 1;
                        heap.push({x + 1, y, 0, dist[x + 1][y]});
                    }
                }
            }
        }
    }
    // for(int i = 1; i <= n; i ++){
    //     for(int j = 1; j <= m; j ++){
    //         if(dist[i][j][1] == inf) cout << "- ";
    //         else cout << dist[i][j][0] << " ";
    //     }
    //     cout << '\n';
    // }
    int ans = dist[edx][edy];
    cout << (ans == inf ? -1 : ans) << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    //cin >> T;
    while(T --){
        solve();
    }
    return 0;
}

加方向

#include<bits/stdc++.h>

#define lc p << 1
#define rc p << 1 | 1
#define lowbit(x) x & -x
#define inv(x) qmi(x, P - 2)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
const int N = 2e5 + 10;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f;
const double PI = 3.141592653;
const ll P = 1e9 + 7;

int T = 1;
ll qmi(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % P;
        b >>= 1;
        a = a * a % P;
    }
    return res;
}
ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}
void print_lll(lll x){
    if(!x) cout << 0 << '\n';
    else{
        vector<int> nums;
        while(x) nums.push_back(x % 10), x /= 10;
        for(int i = 0; i < nums.size(); i ++) cout << nums[i];
    }
}

void print(vector<ll> a, int n){
    for(int i = 0; i < n; i ++){
        if(i < n - 1) cout << a[i] << ' ';
        else cout << a[i];
    }
}

void solve(){
    int n, m, h;
    cin >> n >> m >> h;
    
    vector<vector<char>> g(n + 10, vector<char>(m + 10));
    int stx, sty, edx, edy;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++){
            cin >> g[i][j];
            if(g[i][j] == '*') stx = i, sty = j;
            if(g[i][j] == '%') edx = i, edy = j;
        }
    struct node{
        int x, y, op, d;
        bool operator<(const node&b) const{
            return d > b.d;
        }
    };
    auto check = [&](int x, int y) -> int{
        return (x >= 1 && y >= 1 && x <= n && y <= m);  
    };
    
    //这里注意：3个方向，dist只开2维会把不同方向的dist覆盖掉
    vector<vector<vector<int>>> dist(n + 10, vector<vector<int>>(m + 10, vector<int>(5, inf)));
    priority_queue<node> heap;
    heap.push({stx, sty, 0, 0});
    dist[stx][sty][0] = 0;
    while(heap.size()){
        node t = heap.top();
        heap.pop();
        int x = t.x, y = t.y, op = t.op, d = t.d;
        int ly = y - 1, ry = y + 1;            
        int nex = x + 1, ney = y;
        if(!check(nex, ney)) continue;
        if(!op){
            if(g[nex][ney] == '#'){
                if(check(x, ly) && g[x][ly] != '#' && dist[x][ly][1] > d + 1){
                    dist[x][ly][1] = d + 1;
                    heap.push({x, ly, 1, dist[x][ly][1]});
                }
                if(check(x, ry) && g[x][ry] != '#' && dist[x][ry][2] > d + 1){
                    dist[x][ry][2] = d + 1;
                    heap.push({x, ry, 2, dist[x][ry][2]});
                }
                if(dist[nex][ney][0] > d + h + 1){
                    dist[nex][ney][0] = d + h + 1;
                    heap.push({nex, ney, 0, dist[nex][ney][0]});
                }
            }
            else{
                if(dist[x + 1][y][0] > d + 1){
                    dist[x + 1][y][0] = d + 1;
                    heap.push({x + 1, y, 0, dist[x + 1][y][0]});
                }
            }
        }
        else if(op == 1){
            if(g[x + 1][y] == '#'){
                if(check(x, ly) && g[x][ly] != '#' && dist[x][ly][1] > d + 1){
                    dist[x][ly][1] = dist[x][y][1] + 1;
                    heap.push({x, ly, 1, dist[x][ly][1]});
                }
            }
            else{
                if(dist[x + 1][y][0] > d + 1){
                    dist[x + 1][y][0] = d + 1;
                    heap.push({x + 1, y, 0, dist[x + 1][y][0]});
                }
            }
        }
        else{
            if(check(x + 1, y)){
                if(g[x + 1][y] == '#'){
                    if(check(x, ry) && g[x][ry] != '#' && dist[x][ry][2] > d + 1){
                        dist[x][ry][2] = d + 1;
                        heap.push({x, ry, 2, dist[x][ry][2]});
                    }
                }
                else{
                    if(dist[x + 1][y][0] > d + 1){
                        dist[x + 1][y][0] = d + 1;
                        heap.push({x + 1, y, 0, dist[x + 1][y][0]});
                    }
                }
            }
        }
    }
    // for(int i = 1; i <= n; i ++){
    //     for(int j = 1; j <= m; j ++){
    //         if(dist[i][j][1] == inf) cout << "- ";
    //         else cout << dist[i][j][0] << " ";
    //     }
    //     cout << '\n';
    // }
    int ans = inf;
    for(int i = 0; i < 3; i ++) ans = min(ans, dist[edx][edy][i]);
    cout << (ans == inf ? -1 : ans) << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    //cin >> T;
    while(T --){
        solve();
    }
    return 0;
}