#include "locmin.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<vector<ll>> valarr;

std::pair <int, int> find_locmin_point(int height, int width)
{
    bool found = false;
    valarr.assign(height, vector<ll>(width, -1));
    ll i = 0, j = 0, cur;
    valarr[0][0] = value(i+1, j+1);
    ll val = valarr[0][0];
    while(true)
    {
        found = false;
        for(ll it = 1; it <= 4 && !found; it++)
        {
            ll ni = it == 1 ? i+1 : it == 3 ? i-1 : i;
            ll nj = it == 2 ? j+1 : it == 4 ? j-1 : j;
            if(ni < 0 || ni >= height || nj < 0 || nj >= width) continue;
            cur = valarr[ni][nj] != -1 ? valarr[ni][nj] : valarr[ni][nj] = value(ni+1, nj+1);
            if(cur < val)
            {
                found = true;
                i = ni;
                j = nj;
                val = cur;
            }
        }
        if(!found)
        {
            return {i+1, j+1};
        }
    }
}