Cod sursa(job #390990)

Utilizator loginLogin Iustin Anca login Data 4 februarie 2010 21:33:00
Problema Piese Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
# include <fstream>
using namespace std;
int n, m, a[505][505], nmax, v[9]={1, 2, 4, 8, 16, 32, 64, 128, 256};
ofstream fout ("piese.out");

void read ()
{
	ifstream fin ("piese.in");
	fin>>n>>m;
}

void afis ()
{
	fout<<nmax<<endl;
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
			fout<<a[i][j]<<" ";
		fout<<endl;
	}
}

void umple (int is, int js, int ij, int jj)
{
	for (int i=is;i<=ij;i++)
		for (int j=js;j<=jj;j++)
			a[i][j]=nmax;
}

void solve (int is, int js, int ij, int jj)
{
	int i=8, iii, jjj;
	while (v[i]>jj-js+1 || v[i]>ij-is+1 && i>=0)
		i--;
	++nmax;
	umple(is, js, is+v[i]-1, js+v[i]-1);
	if (v[i]!=jj-js+1 || v[i]!=ij-is+1)
	{
		iii=is+v[i];
		jjj=js+v[i];
		if ((ij-is+1)*(ij-iii+1)>(jj-js+1)*(jj-jjj+1))
		{
	    	if (ij-iii+1 && jj-js+1) solve (iii, js, ij, jj);
			if (iii-is && jj-jjj+1)  solve (is, jjj, iii-1, jj);
		}
		else
		{
			if (ij-iii+1 && jjj-js)  solve (iii, js, ij, jjj-1);
			if (ij-is+1 && jj-jjj+1) solve (is, jjj, ij, jj);
		}
	}
}
	
int main ()
{
	read ();
	solve (1, 1, n, m);
	afis ();
	return 0;
}