#include "locmin.h"
#include <bits/stdc++.h>
const int di[] = {-1, 0, 1,  0};
const int dj[] = { 0, 1, 0, -1};

bool inside(int N, int M, int lin, int col) {
    return 1 <= lin && lin <= N && 1 <= col && col <= M;
}

std::pair <int, int> find_locmin_point(int N, int M) {
    int lin = N / 2, col = 1;
    long long mat[N + 2][M + 2] = { 0 };
    while(true) {
        if(mat[lin][col] == 0) {
            mat[lin][col] = value(lin, col);
        }
        int nr = 0;
        for(int k = 0; k < 4; k++) {
            int newlin = lin + di[k];
            int newcol = col + dj[k];
            if(inside(N, M, newlin, newcol) && mat[newlin][newcol] == 0) {
                mat[newlin][newcol] = value(newlin, newcol);
            }
            if(!inside(N, M, newlin, newcol) || mat[newlin][newcol] > mat[lin][col]) {
                nr++;
            }
            else if(inside(N, M, newlin, newcol) && mat[newlin][newcol] <= mat[lin][col]) {
                lin = newlin;
                col = newcol;
                break;
            }
        }
        if(nr == 4) {
            return {lin, col};
        }
    }
}