#include<iostream>
#include <cmath>
#include <climits>
#include <deque>

using namespace std;

int v[1001][1001];
float table[1002][1002];

int metro(int n,int m,int k){
    deque<int> qi,qj;
    qi.push_back(1);
    qj.push_back(1);
    table[1][1] = 0;
    while(!qi.empty()){
        int i = qi.front(),j = qj.front();
        qi.pop_front();
        qj.pop_front();
        if(i <= n && table[i+1][j] > table[i][j]+100){
            qi.push_back(i+1);
            qj.push_back(j);
            table[i+1][j] = table[i][j]+100;
        }
        if(j <= m && table[i][j+1] > table[i][j]+100){
            qi.push_back(i);
            qj.push_back(j+1);
            table[i][j+1] = table[i][j]+100;
        }
        if(v[i][j] == 1){
            if(i <= n && j <= m && table[i+1][j+1] > table[i][j] + 141.4){
                qi.push_back(i+1);
                qj.push_back(j+1);
                table[i+1][j+1] = table[i][j]+(141.4);
            }
        }
    }
    return ceil(table[n+1][m+1]);
}

int main(){
    int n = 0,m = 0,k = 0;
    cin>>n>>m;
    for(int i = 0;i <= n+1;++i){
        for(int j = 0;j <= m+1;++j){
            v[i][j] = 0;
            table[i][j] = INT_MAX;
        }
    }
    cin>>k;
    for(int i = 0;i < k;++i){
        int x = 0,y = 0;
        cin>>x>>y;
        v[x][y] = 1;
    }
    cout<<metro(n,m,k)<<endl;
    return 0;
}

Edited by author 29.08.2016 16:40

Edited by author 29.08.2016 16:40