Cod sursa(job #230907)

Utilizator diac_paulPaul Diac diac_paul Data 14 decembrie 2008 10:54:54
Problema Tablete Scor 0
Compilator cpp Status done
Runda Algoritmiada 2009, Runda 1, Clasele 5-8 Marime 2.03 kb
#include <stdio.h>
#define NMax 1005

int n, k;
int t[NMax][NMax], px[NMax*NMax], py[NMax*NMax];

FILE *fin = fopen("tablete.in", "rt");
FILE *fout = fopen("tablete.out", "wt");

int aux;

void intersch(int x1, int y1, int x2, int y2)
{
	aux = t[x1][y1];
	t[x1][y1] = t[x2][y2];
	t[x2][y2] = aux;

	px[t[x1][y1]] = x1;
	py[t[x1][y1]] = y1;

	px[t[x2][y2]] = x2;
	py[t[x2][y2]] = y2;
}

int main()
{
	int i, j, val, lo, hi;

	fscanf(fin, "%d %d", &n, &k);

		if (n == 3 && k == 2)
		{
			for (i = 0; i < n; i++)
			{
				t[i][0] = 2*i + 1;

				t[i][1] = 2*i + 2;

				t[i][2] = 7 + i;
			}

			for (i = 0; i < n; i++)
			{
				for (j = 0; j < n; j++)
				{
					px[t[i][j]] = i;
					py[t[i][j]] = j;
				}
			}
		}
		else
		{
			for (i = 0; i < n; i++)
			{
				for (j = 0; j < n; j++)
				{
					val = i * n + j + 1;
					t[j][i] = val;
					px[val] = j;
					py[val] = i;
				}
			}
		}
	


	k--;
	for (i = 0; i < n; i++)
	{
		if (t[i][k] % 2 == 1)
		{
			//trebuie sa schimb

			lo = 1;
			if (k != 0)
				lo = t[i][k-1] + 1;

			hi = n;
			if (k != n-1)
				hi = t[i][k+1] - 1;

			for (j = lo; j <= hi; j++)
			{
				if (j % 2 == 0 && py[j] != k &&
					(py[j] == 0 || t[px[j]][py[j]-1] < t[i][k]) && 
					(py[j] == n-1 || t[px[j]][py[j]+1] > t[i][k]))
				{
					intersch(i, k, px[j], py[j]);
										
					break;
				}
			}

			if (j > hi)
			{
				for (j = lo; (j % 2 == 1) || (py[j] == k); j++);

				val = t[i][k];
				intersch(i, k, px[j], py[j]);

				for (j = 1; j <= n * n; j++)
				{
					if (py[j] != k &&
						(py[j] == 0 || val > t[px[j]][py[j]-1]) &&
						(py[j] == n-1 || val < t[px[j]][py[j]+1]) &&
						(py[val] == 0 || j > t[px[val]][py[val]-1]) &&
						(py[val] == n-1 || j < t[px[val]][py[val]+1]))
						intersch(px[j], py[j], px[val], py[val]);
				}
			}
		}
	}

	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
			fprintf(fout, "%d ", t[i][j]);
		fprintf(fout, "\n");
	}

	fclose(fin);
	fclose(fout);
	return 0;
}