Submission

Score: 0

User: meme_boi2

Problemset: อัศวินขี่ม้าขาว

Language: cpp

Time: 0.002 second

Submitted On: 2025-11-02 23:31:30

#include <bits/stdc++.h>
using namespace std;
#define tii tuple<int,int,int,int>
int32_t main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    int m, n;
    cin >>m  >> n;
    int mat[m][n];
    vector<vector<int>> dp(m,vector<int>(n,INT_MAX));
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            cin >> mat[i][j];
        }
    }
    priority_queue<tii> pq; //{need,cur,i,j}
    if(mat[0][0] <= 0) pq.push({abs(mat[0][0]) + 1,1,0,0});
    else pq.push({1,mat[0][0]+1,0,0});
    while(!pq.empty()){
        auto [need,cur,i,j] = pq.top();
        pq.pop();
        if(dp[i][j] > need) dp[i][j] = need;
        //cout << "need :" << need <<" cur : " << cur << " cord " << i << ' ' << j << '\n';
        if(i + 1 < m){
            if(mat[i+1][j] < 0){
                if(cur+mat[i+1][j] <= 0){
                    if(abs(cur+mat[i+1][j])+1+need >= dp[i+1][j]) continue;
                    pq.push({abs(cur+mat[i+1][j])+1+need,1,i+1,j});
                }else{
                    if(need >= dp[i+1][j]) continue;
                    pq.push({need,cur+mat[i+1][j],i+1,j});
                    
                }
            }else{
                if(need >= dp[i+1][j]) continue;
                else{
                    pq.push({need,cur+mat[i+1][j],i+1,j});
                }
            }
        }
        if(j + 1 < n){
            if(mat[i][j+1] < 0){
                if(cur+mat[i][j+1] <= 0){
                    if(abs(cur+mat[i][j+1])+1+need >= dp[i][j+1]) continue;
                    pq.push({abs(cur+mat[i][j+1])+1+need,1,i,j+1});
                }else{
                   // cout << cur + mat[i][j] << '\n';
                    if(need >= dp[i][j+1]) continue;
                    pq.push({need,cur+mat[i][j+1],i,j+1});
                     
                }
            }else{
                if(need >= dp[i][j+1]) continue;
                else{
                    pq.push({need,cur+mat[i][j+1],i,j+1});
                }
            }
        }
    }
    cout << dp[m-1][n-1];
}
/*
3 3 
-2 -3 3
-5 -10 1 
10 30 -5

2 3
3 -20 30
-3 4 0
*/