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

using namespace std;
using ll = long long;
const int NMAX = 500;

int n, m;
ll v[NMAX + 2][NMAX + 2];

int dl[] = {-1, 0, 1, 0};
int dc[] = {0, -1, 0, 1};
bool inbound(int i, int j) {
    if(i < 1 || j < 1 || i > n || j > m)
        return false;
    return true;
}

bool incercam(int i, int j) {
    for(int d = 0; d < 4; d++) {
        int lin = dl[d] + i;
        int col = dc[d] + j;
        if(inbound(lin, col) && v[lin][col] != -1 && v[lin][col] <= v[i][j])
            return false;
    }
    return true;
}

pair <int, int> find_locmin_point (int _n, int _m) {
    n = _n;
    m = _m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            v[i][j] = -1;
    vector <int> dir;
    dir.push_back(0);
    dir.push_back(1);
    dir.push_back(2);
    dir.push_back(3);
    while(1) {
        int i = (rand() % n) + 1;
        int j = (rand() % m) + 1;
        // cout << i << " " << j << '\n';
        if(v[i][j] == -1 || incercam(i, j)) { ///incercam
            v[i][j] = value(i, j);
            random_shuffle(dir.begin(), dir.end());
            bool ok = 0;
            for(auto d : dir) {
                int lin = dl[d] + i;
                int col = dc[d] + j;
                if(inbound(lin, col) && v[lin][col] == -1) {
                    // cout << "vecin " << lin << " " << col << '\n';
                    v[lin][col] = value(lin, col);
                    if(v[lin][col] <= v[i][j]) {
                        ok = 1;
                        break;
                    }
                }
            }
            if(!ok)
                return {i, j};
        }
    }
}
/*
3 4
5 3 5 6
10 6 4 10
2 9 8 2
*/