Submission

Score: 100

User: Quaoar

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

Language: cpp

Time: 0.112 second

Submitted On: 2026-01-01 14:27:05

#include <iostream>
#include <algorithm>
using namespace std;

int n , m;
int map[1001][1001];
int dp[1001][1001];
bool visited[1001][1001];


int dfs(int x , int y){
    if (x >= n || y >= m) return 2147483647;

    if (x == n - 1 && y == m - 1){
        return max(1, 1 - map[x][y]);
    }

    //memo
    if (visited[x][y]) return dp[x][y];
    visited[x][y] = true;

    int r = dfs(x , y + 1);
    int d = dfs(x + 1 , y);

    int hp = min(d , r) - map[x][y];

    dp[x][y] = max(hp, 1);

    return dp[x][y];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    for (int i = 0 ; i < n ; i++){
        for (int j = 0 ; j < m ; j++){
            cin >> map[i][j];
        }
    }

    cout << dfs(0,0);
}