#include "osalib.h"

#include <string>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <vector>
#include <deque>
#include <set>

using namespace std;

#define DBG(X)

struct pair_hash {

	template <class T1, class T2>

	std::size_t operator () (const std::pair<T1, T2> &p) const {

		auto h1 = std::hash<T1>{}(p.first);

		auto h2 = std::hash<T2>{}(p.second);



		// Mainly for demonstration purposes, i.e. works but is overly simple

		// In the real world, use sth. like boost.hash_combine

		return h1 ^ h2;

	}

};

const int delta_xy[][2] = { { -1, 0 },{ 1, 0 },{ 0, -1 },{ 0, 1 } };
const int delta_xy_cnt = 4;

inline bool is_inside(int x, int low, int high) {
	return (low <= x && x < high);
}


struct BajtocjaStruct {
	int unique_loop_id = 0;
	int liczba_kupiectw;
	int rows, cols;
	char** board;
	int availability_id[1024][1024] = { { 0 } };
	pair<int, int> jakies_kupiectwo;
	//unordered_map<pair<int, int>, int, pair_hash> kupiectwa;

	BajtocjaStruct(int rows, int cols, char** board) : rows(rows), cols(cols), board(board) {
		liczba_kupiectw = 0;

		for (int i = 0; i < rows; i++) {
			for (int j = 0; j < cols; j++) {
				if (board[i][j] == 'K') {
					jakies_kupiectwo.first = i;
					jakies_kupiectwo.second = j;
					liczba_kupiectw++;
					//kupiectwa[make_pair(i, j)] = 1;
				}
				
				availability_id[i][j] = unique_loop_id;
			}
		}
	}

	void bfs(int r, int c, int number)
	{

	}

	void print() {
		printf("Bajtocja:\n");
		for (int i = 0; i < rows; i++) {
			for (int j = 0; j < cols; j++) {
				printf("%c", board[i][j]);
			}
			printf("\n");
		}
	}

	void ile_kupiectw_w_obszarze(int r1, int c1, int r2, int c2)
	{

	}

	int attempt_slow(int nowa_warownia_r, int nowa_warownia_c)
	{
		unique_loop_id += 1;
		pair<int, int> pierwsza_osada = jakies_kupiectwo;
		deque < pair<int, int> > Q;
		Q.push_back(pierwsza_osada);
		int odwiedzonych_kupiectw = 1;
		availability_id[pierwsza_osada.first][pierwsza_osada.second] = unique_loop_id;
		board[nowa_warownia_r][nowa_warownia_c] = 'W';

		while (!Q.empty())
		{
			if (liczba_kupiectw == odwiedzonych_kupiectw)
			{
				break;
			}
			pair<int, int> pole = Q.front();
			Q.pop_front();
			for (int i = 0; i < delta_xy_cnt; i++)
			{
				int nx = pole.first + delta_xy[i][0];
				int ny = pole.second + delta_xy[i][1];
				if (!is_inside(nx, 0, rows) || !is_inside(ny, 0, cols)) {
					continue;
				}
				char c = board[nx][ny];
				if (c == 'W') {
					continue;
				}
				// IDEA: idz bardziej w kierunku innych warowni
				if (availability_id[nx][ny] == unique_loop_id) {
					// juz przetworzona
					continue;
				}

				Q.push_back(make_pair(nx, ny));
				availability_id[nx][ny] = unique_loop_id;
				
				if (c == 'K')
				{
					odwiedzonych_kupiectw++;
				}
			}
		}
		if (liczba_kupiectw == odwiedzonych_kupiectw)
		{
			return 1;
		}
		// nie mozna wybudowac osady
		board[nowa_warownia_r][nowa_warownia_c] = '.';
		return 0;
	}

	bool wolne(int i, int j)
	{
		if (!is_inside(i, 0, rows) || !is_inside(j, 0, cols)) {
			return false;
		}
		return board[i][j] != 'W';
	}

	bool limited_bfs(int start_r, int start_c, int target_r, int target_c, int max_steps, int mark_id)
	{
		/*auto closest_cmp = [target_r, target_c](pair<int, int> a, pair<int, int> b) { 
			int dist_a = abs(a.first - target_r) + abs(a.second - target_r);
			int dist_b = abs(b.first - target_r) + abs(b.second - target_r);
		};
		set<pair<int,int>, decltype(cmp)> Q(closest_cmp);*/

		deque<pair<int, int> > Q;
		Q.push_back(make_pair(start_r, start_c));
		int steps = 0;
		while (!Q.empty())
		{
			pair<int, int> pole = Q.front();
			Q.pop_front();
			steps++;
			if (steps > max_steps) {
				return false;
			}
			for (int i = 0; i < delta_xy_cnt; i++)
			{
				int nr = pole.first + delta_xy[i][0];
				int nc = pole.second + delta_xy[i][1];
				if (!wolne(nr, nc)) {
					continue;
				}
				if (availability_id[nr][nc] == mark_id) {
					continue;
				}
				availability_id[nr][nc] = mark_id;
				Q.push_back(make_pair(nr, nc));
				if (nr == target_r && nc == target_c) {
					return true;
				}
			}
		}
		return false;
	}

	int attempt(int nowa_warownia_r, int nowa_warownia_c)
	{
		board[nowa_warownia_r][nowa_warownia_c] = 'W';
		deque < pair<int, int> > Q;
		const int critical_points[][2] = {
			{ -1, 0 },{ 1, 0 },
			{ 0, -1 },{ 0, 1 },
			{ -1, 0}, {0, -1},
			{ 0, -1}, {1, 0},
			{1, 0}, {0, 1},
			{1, 0}, {-1, 0}
		};
		bool heureza = true;
		DBG(printf("Trying board at (%d, %d):\n", nowa_warownia_r, nowa_warownia_c));
		DBG(print());
		for (int i = 0; i < 6; i++) {
			int start_r = nowa_warownia_r + critical_points[i * 2][0];
			int start_c = nowa_warownia_c + critical_points[i * 2][1];
			int target_r = nowa_warownia_r + critical_points[i * 2 + 1][0];
			int target_c = nowa_warownia_c + critical_points[i * 2 + 1][1];
			
			if (wolne(start_r, start_c) && wolne(target_r, target_c)) {
				DBG(printf("(%d, %d) -> (%d, %d) ->", start_r, start_c, target_r, target_c));
				if (!limited_bfs(start_r, start_c, target_r, target_c, 150, ++unique_loop_id)) {
					heureza = false;
					DBG(printf(" false\n"));
					break;
				}
				DBG(printf(" true\n"));
			}
		}
		if (heureza)
		{
			DBG(printf("heureza OK\n"));
			return 1;
		}
		return attempt_slow(nowa_warownia_r, nowa_warownia_c);
	}

	void move_kupiectwo(int r1, int c1, int r2, int c2) 
	{
		board[r1][c1] = '.';
		board[r2][c2] = 'K';
		if (jakies_kupiectwo.first == r1 && jakies_kupiectwo.second == c1) {
			jakies_kupiectwo.first = r2;
			jakies_kupiectwo.second = c2;
		}
	}
};

BajtocjaStruct* bajtocja;

void NowaWyspa(int n, int m, char **board) {
	bajtocja = new BajtocjaStruct(n, m, board);
	DBG(bajtocja->print());
}
/**
prosi o budowę nowej warowni na obszarze o współrzędnych (r, c).
Możesz założyć, że we wskazanym polu znajdują się obecnie tereny uprawne. Funkcja powinna zwrócić 1,
gdy w obecnej chwili można wybudować warownię zgodnie z zasadami. W tym przypadku budowla ta
jest natychmiast wznoszona. W przeciwnym razie funkcja powinna zwrócić 0.

*/
int NowaWarownia(int r, int c) {
	--r; --c;
	int res = bajtocja->attempt(r,c);
	DBG(bajtocja->print());
	return res;
}

/**
wnioskuje o przeniesienie osady kupieckiej
z pola (r1, c1) na pole (r2, c2). Możesz założyć, że na polu (r1, c1) do tej pory była osada, pole (r2, c2)
było niezagospodarowane oraz oba pola są sąsiednie, zatem |r1−r2|+|c1−c2| = 1. W wyniku tej operacji
pole (r1, c1) staje się terenem rolnym, zaś (r2, c2) – osadą.

*/
void PrzeniesOsade(int r1, int c1, int r2, int c2) {
	--r1;--r2;--c1;--c2;
	bajtocja->move_kupiectwo(r1, c1, r2, c2);
	DBG(bajtocja->print());
}