Submission

Score: 0

User: s0m30n3

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

Language: cpp

Time: 0.004 second

Submitted On: 2026-03-18 14:55:12

#include<bits/stdc++.h>
using namespace std;

int table[1005][1005] = {};
vector<vector<int>> bestHP(1005, vector<int>(1005 ,-1));
int dx[2] = {1,0};
int dy[2] = {0,1};
int n,m;

bool check(int x){
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            bestHP[i][j]=-1;
        }
    }
    queue<pair<pair<int,int>, int>> q;
    bestHP[0][0]=x+table[0][0];
    if(bestHP[0][0]<=0) return false;
    q.push({{0,0},bestHP[0][0]});
    while(!q.empty()){
        auto t = q.front();
        auto u = t.first.first;
        auto v = t.first.second;
        auto health = t.second;
        q.pop();
        if(health<0) continue;;
        if(u==n-1&&v==m-1){
           return true;
           break;
        }
        for(int k=0;k<2;k++){
            int ny = u+dy[k];
            int nx = v+dx[k];
            if(ny<0||nx<0||ny>=n||nx>=m) continue;
            auto die = health+table[ny][nx];
            if(die>0&&die>bestHP[ny][nx]){
                 bestHP[ny][nx]=die;
                 q.push({{ny,nx}, die});
            }
        }
    }
    return false;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>table[i][j];
        }
    }
    int l = 0;
    int r = 1e9;
    int answer=0;
    while(l<=r){
        int mid = l + (r-l)/2;
        if(check(mid)){
             answer=mid;
             r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    cout << answer;
}