Submission

Score: 0

User: meme_boi2

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

Language: cpp

Time: 1.120 second

Submitted On: 2025-11-03 07:05:31

#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,vector<tii>,greater<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(i == m-1 && j==n-1){
            cout << need;
            return 0;
        }
     //   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

3 3
3 0 -3
-3 -2 -2
3 1 -3
*/