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

using ll = long long;

const int MAX_N = 500;
const int MAX_M = 500;

int n, m;

ll a[MAX_N + 1][MAX_M + 1];
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

inline bool inside(int x, int y) {
    return x >= 1 && y >= 1 && x <= n && y <= m;
}

std::pair <int, int> find_locmin_point(int N, int M) {
    n = N;
    m = M;

    a[1][1] = value(1, 1);

    int x = 1, y = 1;

    while (true) {
        int px = x, py = y;

        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (!inside(nx, ny)) continue;
            if (!a[nx][ny])
                a[nx][ny] = value(nx, ny);

            if (a[nx][ny] < a[px][py]) {
                px = nx;
                py = ny;
            }
        }

        if (px == x && py == y)
            return std::make_pair(x, y);

        x = px;
        y = py;
    }
}
