F 样例只能过一半求解

#include<bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef long long ll;
int _T = 1;
int dir[2][4] = {{0,0,-1,1},{-1,1,0,0}},n,m;
ll f[5][1005][1005];
char a[1005][1002];
void solve(){
    cin >> n >> m;
    for(int i = 1;i <= n; ++i) {
        for(int j = 1;j <= m; ++j)
        cin >> a[i][j];
    }
    priority_queue <tuple<ll,int,int,int,bool>> q;
    q.push({0,1,1,4,1});
    q.push({0,1,1,0,0});
    q.push({0,1,1,1,0});
    q.push({0,1,1,2,0});
    q.push({0,1,1,3,0});
    for(int i = 0;i < 5; ++ i){
        for(int j = 1;j <= n; ++j) {
            for(int k = 1;k <= m; ++k)
            f[i][j][k] = 1e18;
        }
        f[i][1][1] = 0;
    } 
    while(!q.empty()) {
        auto [d,i,j,k,vis] = q.top();q.pop();
        d = -d;
        if(d > f[k][i][j]) continue;
        for(int w = 0;w < 4; ++ w) {
            if(w == k) continue;
            int x = i + dir[0][w],y = j + dir[1][w];
            if(x < 1 || x  > n || y < 1 || y > m) continue;
            if(f[k][x][y] <= d + 1) continue;
            if(a[x][y] == 'X' && vis) continue; 
            f[k][x][y] = d + 1;
            if(a[x][y] == 'X') q.push({-d-1,x,y,k,1});
            else q.push({-d-1,x,y,k,vis});
        }
    }
    ll res = 1e18;
    for(int i = 0;i < 5; ++ i) res = min(res,f[i][n][m]);
    cout << (res < 1e18 ? res : -1);
}
int main() {
    //cin >> _T;
    while(_T--) {
        solve();
    }
}

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-23 14:22
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务