#include "locmin.h"
#include <utility>

const int MAX_N = 500;
const long long INF = 1e18 + 10;

const int dx[] = { 0, 0, 1, -1 };
const int dy[] = { 1, -1, 0, 0 };

long long a[MAX_N + 2][MAX_N + 2];

std::pair <int, int> find_locmin_point(int N, int M) {
    for (int i = 0; i <= N + 1; i++) {
        a[i][0] = a[i][M + 1] = INF;
    }

    for (int i = 0; i <= M + 1; i++) {
        a[0][i] = a[N + 1][i] = INF;
    }

    std::pair<int, int> cur = { 1, 1 };
    a[1][1] = value(1, 1);

    while (true) {
        bool ok = true;

        for (int d = 0; d < 4; d++) {
            int x = cur.first + dx[d];
            int y = cur.second + dy[d];

            if (a[x][y] == 0) {
                a[x][y] = value(x, y);
            }

            if (a[x][y] < a[cur.first][cur.second]) {
                cur = { x, y };
                ok = false;
                break;
            }
        }

        if (ok) {
            return cur;
        }
    }
}
