#include <bits/stdc++.h>
#include "locmin.h"
using namespace std;
const int PC = 4;
const int MAX = 500;
long long mr[MAX + 2][MAX + 2];
int dl[] = {-1, 0, 0, 1};
int dc[] = {0, -1, 1, 0};
int lin[MAX * MAX], col[MAX * MAX];
long long getValue(int l, int c) {
    if (mr[l][c] == 0) {
        mr[l][c] = value(l, c);
    }
    return mr[l][c];
}
char verif(int l, int c, int n, int m) {
    int i, rez, l2, c2, l3, c3;
    long long x, y, minr;
    minr = getValue(l, c);
    rez = 0;
    while (i < PC) {
        l2 = l + dl[i];
        c2 = c + dc[i];
        if (l2 > 0 && l2 <= n && c2 > 0 && c2 <= m) {

            y = getValue(l2, c2);
            if (y < minr) {
                rez = 1;
                l3 = l2;
                c3 = c2;
                minr = y;
            }
        }
        i++;
    }
    return rez;
}
std::pair <int, int> find_locmin_point(int n, int m) {
    int l, c, i, rez, l2, c2, st, dr, mij, l3, c3, nrc;
    long long x, y, minr;
    /*l = rand() % n + 1;
    c = m / 2 + 1;
    rez = 1;
    while (rez > 0) {
        x = getValue(l, c);
        i = rez = 0;
        l3 = l;
        c3 = c;
        minr = x;
        while (i < PC) {
            l2 = l + dl[i];
            c2 = c + dc[i];
            if (l2 > 0 && l2 <= n && c2 > 0 && c2 <= m) {

                y = getValue(l2, c2);
                if (y < minr) {
                    rez = 1;
                    l3 = l2;
                    c3 = c2;
                    minr = y;
                }
            }
            i++;
        }
        l = l3;
        c = c3;
        x = minr;
    }*/
    nrc = 0;
    for (l = 1; l <= n; l++) {
        for (c = 1; c <= m; c++) {
            lin[nrc] = l;
            col[nrc] = c;
            nrc++;
        }
    }
    rez = 1;
    while (rez > 0) {
        i = rand() % nrc;
        rez = verif(lin[i], col[i], n, m);
        if (rez == 0) {
            l = lin[i];
            c = col[i];
        } else {
            swap(lin[i], lin[nrc - 1]);
            swap(col[i], col[nrc - 1]);
            nrc--;
        }
    }
    //v[st] < v[st - 1] si v[dr] < v[dr + 1]
    //ambele incluse
    /*l = 1;
    getValue(l, 1);
    getValue(l, m);
    st = 1;
    dr = m;
    while (dr - st > 0) {
        mij = (st + dr) / 2;
        getValue(l, mij);
        getValue(l, mij + 1);
        if (mr[l][mij] < mr[l][mij + 1]) {
            dr = mij;
        } else {
            st = mij + 1;
        }
    }*/
    /*if (dr == st + 1) {
        if ()
    }*/
    return {l, c};
}
