Cod sursa(job #265963)

Utilizator nautilusCohal Alexandru nautilus Data 24 februarie 2009 19:48:29
Problema Castel Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.41 kb
#include <fstream.h>

long lst[22801][180],u[22801];

int main()
{
 long n,m,k,i,aux,q[22801],sfc,inc,c,x,j;


 ifstream fin("castel.in");
 fin>>n>>m>>k;


 for (i=1; i<=n*m; i++)
	{
	 u[i]=0;
	 fin>>aux;
	 lst[aux][0]++;
	 lst[aux][lst[aux][0]]=i;
	}

 q[1]=k; inc=0; sfc=1; u[k]=1; c=1;

 while (inc<=sfc)
	{
	 inc++;

	 for (i=1; i<=lst[q[inc]][0]; i++)
		{
		 x=lst[q[inc]][i];
		 if (u[x]==0)
			{
			 //coltul stanga sus
			 if (x==1)
				{
				 if (u[x+1]==1 || u[x+m]==1)
					{
					 u[x]=1;
					 sfc++;
					 q[sfc]=x;
					 c++;
					} else
					{
					 lst[x+1][0]++; lst[x+1][lst[x+1][0]]=x;
					 lst[x+m][0]++; lst[x+m][lst[x+m][0]]=x;
					}
				} else

			 //coltul dreapta sus
			 if (x==m)
				{
				 if (u[x-1]==1 || u[x+m]==1)
					{
					 u[x]=1;
					 sfc++;
					 q[sfc]=x;
					 c++;
					} else
					{
					 lst[x-1][0]++; lst[x-1][lst[x-1][0]]=x;
					 lst[x+m][0]++; lst[x+m][lst[x+m][0]]=x;
					}
				} else

			 //coltul stanga jos
			 if (x==(n-1)*m+1)
				{
				 if (u[x+1]==1 || u[x-m]==1)
					{
					 u[x]=1;
					 sfc++;
					 q[sfc]=x;
					 c++;
					} else
					{
					 lst[x+1][0]++; lst[x+1][lst[x+1][0]]=x;
					 lst[x-m][0]++; lst[x-m][lst[x-m][0]]=x;
					}
				} else

			 //coltul dreapta jos
			 if (x==n*m)
				{
				 if (u[x-1]==1 || u[x-m]==1)
					{
					 u[x]=1;
					 sfc++;
					 q[sfc]=x;
					 c++;
					} else
					{
					 lst[x-1][0]++; lst[x-1][lst[x-1][0]]=x;
					 lst[x-m][0]++; lst[x-m][lst[x-m][0]]=x;
					}
				} else

			 //marginea de sus
			 if (x<=m)
				{
				 if (u[x-1]==1 || u[x+1]==1 || u[x+m]==1)
					{
					 u[x]=1;
					 sfc++;
					 q[sfc]=x;
					 c++;
					} else
					{
					 lst[x-1][0]++; lst[x-1][lst[x-1][0]]=x;
					 lst[x+1][0]++; lst[x+1][lst[x+1][0]]=x;
					 lst[x+m][0]++; lst[x+m][lst[x+m][0]]=x;
					}
				} else

			 //marginea de jos
			 if (x>(n-1)*m)
				{
				 if (u[x-1]==1 || u[x+1]==1 || u[x-m]==1)
					{
					 u[x]=1;
					 sfc++;
					 q[sfc]=x;
					 c++;
					} else
					{
					 lst[x-1][0]++; lst[x-1][lst[x-1][0]]=x;
					 lst[x+1][0]++; lst[x+1][lst[x+1][0]]=x;
					 lst[x-m][0]++; lst[x-m][lst[x-m][0]]=x;
					}
				} else

			 //marginea din stanga
			 if (x%m==1)
				{
				 if (u[x+1]==1 || u[x-m]==1 || u[x+m]==1)
					{
					 u[x]=1;
					 sfc++;
					 q[sfc]=x;
					 c++;
					} else
					{
					 lst[x+1][0]++; lst[x+1][lst[x+1][0]]=x;
					 lst[x-m][0]++; lst[x-m][lst[x-m][0]]=x;
					 lst[x+m][0]++; lst[x+m][lst[x+m][0]]=x;
					}
				} else

			 //marginea din dreapta
			 if (x%m==0)
				{
				 if (u[x-1]==1 || u[x-m]==1 || u[x+m]==1)
					{
					 u[x]=1;
					 sfc++;
					 q[sfc]=x;
					 c++;
					} else
					{
					 lst[x-1][0]++; lst[x-1][lst[x-1][0]]=x;
					 lst[x-m][0]++; lst[x-m][lst[x-m][0]]=x;
					 lst[x+m][0]++; lst[x+m][lst[x+m][0]]=x;
					}
				} else

			 //nu e pe nicio margine
			 //if (x%m!=1 && x%m!=0)
				{
				 if (u[x-1]==1 || u[x+1]==1 || u[x-m]==1 || u[x+m]==1)
					{
					 u[x]=1;
					 sfc++;
					 q[sfc]=x;
					 c++;
					} else
					{
					 lst[x-1][0]++; lst[x-1][lst[x-1][0]]=x;
					 lst[x+1][0]++; lst[x+1][lst[x+1][0]]=x;
					 lst[x-m][0]++; lst[x-m][lst[x-m][0]]=x;
					 lst[x+m][0]++; lst[x+m][lst[x+m][0]]=x;
					}
				}
			}
		}
	}

 ofstream fout("castel.out");
 fout<<c;

 fin.close();
 fout.close();

 return 0;
}