Четвёртый открытый Зеленоградский турнир 2008

#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;

int inp[500][128][128];
vector<int> c, w, h;
vector<vector<pair<int,int> > > outv;

void input(int t)
{
	c.assign(t, 0);
	w = h = c;
	for (int i= 0; i < t; ++i)
	{
		scanf("%d%d%d", &h[i], &w[i], &c[i]);
		for (int j = 0; j < h[i]; ++j)
			for (int k = 0; k < w[i]; ++k)
			{
				scanf("%d", &inp[i][h[i]-j-1][k]);
			}
	}
}

unsigned int was[100][128] = {0};
int x[10000], y[10000];
const int step[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

void Solve(int l)
{
	memset(was, 0, sizeof(was));
	int colorwas[50] = {0};
	int height[50];
	unsigned cnt = 0;
	int n = h[l];
	int m = w[l];
	vector<int> C(c[l], 0);
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			C[inp[l][i][j]]++;

	int c = 0;
	while (true)
	{
		bool foundlittle = false;
		unsigned curc = cnt;
		++cnt;
		int bestc = -1, bestx, besty, bests, bestcnt, bminj, bmaxj, bmini;
		for (int i = n-1-c; i >= 0/* && inp[l][i][j] != -1*/; --i)
		{
			bool b = true;
			for (int j = 0; j < m; ++j)
			{
				if (inp[l][i][j] != -1 && was[i][j] <= curc)
				{
					b = false;
					++cnt;
					was[i][j] = cnt;
					int color = inp[l][i][j];
					if (bestc != -1 && C[color] > C[bestc]) continue;
					x[0] = i; y[0] = j;
					int mini = i, minj = j, maxj = j;
					int r = 0, w = 1;
					while (r < w)
					{
						for (int k = 0; k < 4; ++k)
						{
							int newx = x[r]+step[k][0];
							int newy = y[r]+step[k][1];
							if (newx >= 0 && newy >= 0 && newx < n && newy < m && inp[l][newx][newy] == color && was[newx][newy] != cnt)
							{
								mini = min(mini, newx);
								minj = min(minj, newy);
								maxj = max(maxj, newy);
								was[newx][newy] = cnt;
								x[w] = newx; y[w] = newy;
								++w;
							}
						}
						++r;
					}
					if (w > 1 && w < 5 && colorwas[color] != 0)
					{
						bestc = color;
						bests = w;
						bestcnt = cnt;
						bminj = minj; bmaxj = maxj; bmini = mini;
						bestx = i; besty = j;
						foundlittle = true;
						break;
					}
					if (w > 1 && (bestc == -1 || C[color] < C[bestc] || C[color] == C[bestc] && w <= bests))
					{
						bestc = color;
						bests = w;
						bestcnt = cnt;
						bminj = minj; bmaxj = maxj; bmini = mini;
						bestx = i; besty = j;
					}
				}
			}
			if (foundlittle) break;
			if (b == true && i == n-1-c)
			{
				++c;
			}
		}
		if (bestc == -1)
		{
			return;
		}
		else 
		{
			colorwas[bestc] = 1;
			C[bestc] -= bests;
			outv[l].push_back(make_pair(n-bestx-1, besty));
			for (int j = bminj; j <= bmaxj; ++j)
			{
				int r = bmini;
				for (int i = bmini; i < n && inp[l][i][j] != -1; ++i)
				{
					if (was[i][j] != bestcnt)
					{
						inp[l][r][j] = inp[l][i][j];
						++r;
					}
				}
				while (r < n && inp[l][r][j] != -1) {inp[l][r][j] = -1; ++r;}
			}
		}
	}
}


int main()
{
	int t;
	scanf("%d", &t);
	outv.resize(t);
	input(t);
	const int TESTS = 75;
	vector<int> was(t, 0); 
	for (int i = 0; i < min(t, TESTS); ++i)
	{
		//double maxc = 0, best = -1;
		//for (int j = 0; j < t; ++j)
		//	if (was[j] == 0 && w[j]*h[j] / (double)(c[j]*c[j]*c[j]*c[j]*c[j]) > maxc)
		//	{
		//		maxc = w[j]*h[j] / (double)(c[j]*c[j]*c[j]*c[j]*c[j]);
		//		best = j;
		//	}
		int minc = 1000, best = -1;
		for (int j = 0; j < t; ++j)
			if (was[j] == 0 && (c[j] < minc || c[j] == minc && w[best]*h[best] < w[j]*h[j]))
			{
				minc = c[j];
				best = j;
			}
		was[best] = 1;
		Solve(best);
	}
	for (int i = 0; i < t; ++i)
	{
		printf("Y\n");
		for (int j = 0; j < outv[i].size(); ++j)
		{
			printf("%d %d\n", outv[i][j].first, outv[i][j].second);
		}
		printf("-1 -1\n");
	}
	return 0;
}