#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <thread>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <windows.h>
#include <thread>

using namespace std;

struct district;
struct region;
struct area;
struct party;

bool compare_parties(party* p1, party* p2);

//#define DEBUG_INPUT
//#define DEBUG_BORDER
#define DEBUG_STATE

unsigned short n;
unsigned short d;
unsigned short p;
unsigned short r;

district** table[8];
unsigned short** result[8];
vector<region*> region_list[8];
unordered_set<district*>* border_list;
vector<district*> consumed_list[8];
unordered_set<district*> unconsumed_set[8];

std::thread* thread_list;

struct district {
	unsigned short x;
	unsigned short y;
	unsigned short party_id;
	region* reg;
};

struct party {
	unsigned short party_id;
	unsigned short size;
};

struct region {
	unsigned short id = 0;
	unsigned short thread_id = 0;
	vector<district*> dis_list = vector<district*>();
	unordered_set<district*> dis_set = unordered_set<district*>();
	unordered_set<district*> neighbor_set;
	vector<party*> party_list = vector<party*>(p);
	party* party_ref;

	region(district *dis, unsigned short region_id, unsigned short thread_id) {
		this->thread_id = thread_id;
		for (int i = 0; i < p; i++) {
			party_list[i] = new party();
			party_list[i]->party_id = i;
			if (i == dis->party_id) {
				party_list[i]->size = 1;
			} else {
				party_list[i]->size = 0;
			}

			if (dis->party_id == i) {
				party_ref = party_list[i];
			}
		}
		neighbor_set = unordered_set<district*>();

		unsigned short border_list[4][2] = {
			{dis->x - (unsigned short)1, dis->y} ,
			{dis->x, dis->y - (unsigned short)1} ,
			{dis->x, dis->y + (unsigned short)1} ,
			{dis->x + (unsigned short)1, dis->y}
		};

		for (unsigned short i = 0; i < 4; i++) {
			unsigned short x = border_list[i][0];
			unsigned short y = border_list[i][1];

			if (x >= 0 && x < n && y >= 0 && y < n) {

				district* newdis = &table[thread_id][y][x];

				if (newdis->reg != NULL) {
					continue;
				}

				neighbor_set.insert(newdis);
			}
		}
		sort(party_list.begin(), party_list.end(), compare_parties);

		id = region_id;
		dis->reg = this;
		dis_list.push_back(dis);
		dis_set.insert(dis);
	}

	bool fast_add_district(district* dis) {
		if (dis->reg == NULL) {
			dis_set.insert(dis);
			return true;
		}
		return false;
	}

	bool add_district(district* dis) {
		if (dis->reg != NULL) {
			return false;
		}

		dis->reg = this;
		dis_list.push_back(dis);
		dis_set.insert(dis);

		for (party* pa : party_list) {
			if (pa->party_id == dis->party_id) {
				pa->size++;
			}
		}

		sort(party_list.begin(), party_list.end(), compare_parties);

		unordered_set<district*>* dis_heighbors = new unordered_set<district*>();
		dis_heighbors->reserve(4);

		unsigned short border_list[4][2] = {
			{(int)dis->x - 1, (int)dis->y} ,
			{(int)dis->x, (int)dis->y - 1} ,
			{(int)dis->x, (int)dis->y + 1} ,
			{(int)dis->x + 1, (int)dis->y}
		};

		for (unsigned short i = 0; i < 4; i++) {
			unsigned short x = border_list[i][0];
			unsigned short y = border_list[i][1];

			if (x >= 0 && x < n && y >= 0 && y < n) {

				district* newdis = &table[thread_id][y][x];

				if (newdis->reg != NULL) {
					continue;
				}

				dis_heighbors->insert(newdis);
			}
		}

		neighbor_set.insert(dis_heighbors->begin(), dis_heighbors->end());
		neighbor_set.erase(dis);

		delete dis_heighbors;

		return true;
	}

	unordered_set<district*>* get_neighbor_set(district* dis, unordered_set<district*> exclude_set, unordered_set<district*> include_set) {

		unordered_set<district*>* result = new unordered_set<district*>();
		result->reserve(4);

		unsigned short border_list[4][2] = {
			{dis->x - 1, dis->y} ,
			{dis->x, dis->y - 1} ,
			{dis->x, dis->y + 1} ,
			{dis->x + 1, dis->y}
		};

		for (unsigned short i = 0; i < 4; i++) {
			unsigned short x = border_list[i][0];
			unsigned short y = border_list[i][1];

			if (x >= 0 && x < n && y >= 0 && y < n) {

				district* newdis = &table[thread_id][y][x];

				if (newdis->reg != NULL) {
					continue;
				}

				result->insert(newdis);
			}
		}

		return result;
	}
};

void read_input(string inputFile) {
	ifstream infile(inputFile);

	string line;
	getline(infile, line);
	istringstream iss(line);

	iss >> n >> d >> p;
	r = n * n / d;

	border_list = new unordered_set<district*>[p];
	for (unsigned short i = 0; i < p; i++) {
		border_list[i] = unordered_set<district*>();
		unconsumed_set[i] = unordered_set<district*>();
		consumed_list[i] = vector<district*>();

		table[i] = new district * [n];
		result[i] = new unsigned short* [n * p];

		for (unsigned short j = 0; j < n * p; j++) {
			result[i][j] = new unsigned short[n];
		}
	}

	unsigned short row_index = 0;

	while (getline(infile, line))
	{
		istringstream iss(line);

		table[0][row_index] = new district[n];

		for (unsigned short i = 0; i < n; i++) {
			iss >> table[0][row_index][i].party_id;
			table[0][row_index][i].party_id--;
			table[0][row_index][i].x = i;
			table[0][row_index][i].y = row_index;
			table[0][row_index][i].reg = NULL;
			unconsumed_set[0].insert(&table[0][row_index][i]);
		}

		for (unsigned short i = 1; i < p; i++) {
			table[i][row_index] = new district[n];
			for (unsigned short j = 0; j < n; j++) {
				table[i][row_index][j].party_id = table[0][row_index][j].party_id;

				table[i][row_index][j].x = j;
				table[i][row_index][j].y = row_index;
				table[i][row_index][j].reg = NULL;
				unconsumed_set[i].insert(&table[i][row_index][j]);
			}
		}

		row_index++;
	}
}

void find_border(unsigned short party_id) {

	border_list[party_id] = unordered_set<district*>();

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (table[party_id][i][j].party_id == party_id) {

				if (i - 1 >= 0) {
					if (table[party_id][i - 1][j].party_id != party_id) {
						border_list[party_id].insert(&table[party_id][i][j]);
					}
				}

				if (i + 1 < n) {
					if (table[party_id][i + 1][j].party_id != party_id) {
						border_list[party_id].insert(&table[party_id][i][j]);
					}
				}

				if (j - 1 >= 0) {
					if (table[party_id][i][j - 1].party_id != party_id) {
						border_list[party_id].insert(&table[party_id][i][j]);
					}
				}

				if (j + 1 < n) {
					if (table[party_id][i][j + 1].party_id != party_id) {
						border_list[party_id].insert(&table[party_id][i][j]);
					}
				}
			}
		}
	}

#ifdef DEBUG_BORDER
	cout << "================================== Border ==================================" << endl;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (border_list[party_id - 1].find(&table[i][j]) != border_list[party_id - 1].end()) {
				cout << "1 ";
			}
			else {
				cout << "0 ";
			}
		}
		cout << endl;
	}
	cout << endl;
#endif
}

bool compare_parties(party *p1, party *p2)
{
	return (p1->size > p2->size);
}

list<district*> sort_prefered_next_region(region* reg) {

	if (reg->neighbor_set.size() == 0) {
		return list<district*>();
	}

	unordered_set<district*> potential_list = reg->neighbor_set;

	list<district*> prefered_list = list<district*>();
	
	if (reg->party_ref->size <= reg->party_list[1]->size + 1) {

		for (district* dis : potential_list) {
			if (dis->party_id == reg->party_ref->party_id && reg->party_ref->size == reg->party_list[0]->size) {
				if (border_list[reg->thread_id].find(dis) == border_list[reg->thread_id].end()) {
					prefered_list.push_back(dis);
				}
			}
		}

		for (district* dis :prefered_list) {
			potential_list.erase(dis);
		}

		for (district* dis : potential_list) {
			if (dis->party_id == reg->party_ref->party_id) {
				prefered_list.push_back(dis);
			}
		}

		for (district* dis : prefered_list) {
			potential_list.erase(dis);
		}
	}

	for (district* dis : potential_list) {
		if (dis->party_id != reg->id) {
			for (party* pa : reg->party_list) {
				if (pa == reg->party_ref && pa->size < reg->party_ref->size - 1) {
					prefered_list.push_back(dis);
				}
			}
		}
	}

	for (district* dis : prefered_list) {
		potential_list.erase(dis);
	}

	for (district* dis : potential_list) {
		if (dis->party_id != reg->party_ref->party_id) {
			prefered_list.push_back(dis);
			break;
		}
	}

	for (district* dis : prefered_list) {
		potential_list.erase(dis);
	}
	
	for (district* dis : potential_list) {
		prefered_list.push_back(dis);
	}

	return prefered_list;
}

void build_important_region(region* reg) {
	
	for (unsigned short i = reg->dis_list.size(); i < r; i++) {
		list<district*> next_reg_list = sort_prefered_next_region(reg);

		for (district* dis : next_reg_list) {
			if (dis->reg == NULL) {
				reg->add_district(dis);
				consumed_list[reg->thread_id].push_back(dis);
				unconsumed_set[reg->thread_id].erase(dis);
				break;
			}
		}
	}
}

void build_rest_region(region* reg) {

	for (unsigned short i = reg->dis_list.size(); i < r; i++) {

		for (district* dis : reg->neighbor_set) {
			if (dis->reg == NULL) {
				reg->add_district(dis);
				consumed_list[reg->thread_id].push_back(dis);
				unconsumed_set[reg->thread_id].erase(dis);
				break;
			}
		}
	}
}

void build(unsigned short thread_id) {
	vector<district*> starting_points = vector<district*>();
	unsigned short i = 0;

	for (district* dis : border_list[thread_id]) {

		if (i >= d) {
			break;
		}

		if (dis->reg == NULL) {
			starting_points.push_back(dis);
		}
		i++;
	}

	random_shuffle(starting_points.begin(), starting_points.end());

	int region_id = 0;
	for (district* dis : starting_points) {
		if (dis->reg == NULL) {
			region* reg = new region(dis, region_id + 1, thread_id);
			region_list[thread_id].push_back(reg);
			build_important_region(reg);

			region_id++;

			if (region_id == d) {
				break;
			}
		}
	}

	while (region_id < d) {
		bool has_processed_region = false;
		for (district* dis : unconsumed_set[thread_id]) {
			if (dis->reg == NULL) {
				region* reg = new region(dis, region_id + 1, thread_id);
				region_list[thread_id].push_back(reg);
				build_rest_region(reg);
				has_processed_region = true;
				break;
			}
		}
		if (!has_processed_region) {
			break;
		}
		region_id++;
	}
}

int main() {

	read_input("gerrymandering.in");

	for (unsigned short i = 0; i < p; i++) {
		find_border(i);
	}

	thread_list = new std::thread[p];

	for (unsigned short i = 0; i < p; i++) {
		thread_list[i] = std::thread(build, i);
	}

	for (unsigned short i = 0; i < p; i++) {
		thread_list[i].join();
	}
	
#ifdef DEBUG_STATE
	//cout << "================================== State ==================================" << endl;
	//for (int th = 0; th < p; th++) {
	//	for (int i = 0; i < n; i++) {
	//		for (int j = 0; j < n; j++) {
	//			if (table[th][i][j].reg != NULL) {
	//				if (table[th][i][j].reg->id < 10) {
	//					cout << " " << table[th][i][j].reg->id << " ";
	//				}
	//				else {
	//					cout << table[th][i][j].reg->id << " ";
	//				}
	//			}
	//			else {
	//				cout << " 0 ";
	//			}
	//		}
	//		cout << endl;
	//	}
	//	cout << endl;
	//}
#endif
}