Timus-DP

1119.cpp

#include <iostream>
#include <map>
#include <unordered_map>
#include <utility>
#include <vector>
#include <limits.h>
#include <float.h>
#include <math.h>
using namespace std;
int r, c;
double vis[1009][1009];
map < pair< int, int >, int> tr;


double solve(int x, int y){
   if(vis[x][y] != 0.0) return vis[x][y];
    if(x == c && y == r) return 0.0;
    vis[x][y] = 1;
    double ans1 =   DBL_MAX, ans2 = DBL_MAX, ans3 = DBL_MAX;
    if(x + 1 <= c) ans1 = 100.0 + solve(x + 1, y);
    if(y + 1 <= r) ans2 = 100.0 + solve(x, y + 1);
    
    if(tr[{x + 1, y + 1}]) ans3 = 141.421356237 + solve(x + 1, y + 1);
    return vis[x][y] = min( ans1, min(ans2, ans3) );
}

int main()
{
    cin >> c >> r;
    int k; cin >> k;
    int t1, t2;

    while(k--){
        cin >> t1 >> t2;
        tr[{t1, t2}] = true;
    }

    cout << round(solve(0, 0)) << endl;

    


    return 0;
}

//judge ID: 249119DJ