Cod sursa(job #251912)

Utilizator robigiirimias robert robigi Data 3 februarie 2009 16:43:07
Problema Castel Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <fstream.h>

ifstream f ("castel.in");
ofstream g ("castel.out");

typedef struct
	{  int x, y, ce, cn, k;
	}cheie;

cheie c[32768];

int n, m, k, v[152][152], s[32768], I, J, xx, yy, cc, cv=1;
int dx[4]={-1, 0, 1, 0}, dy[4]={0, 1, 0, -1}, dc[4]={-m, 1, m, -1};

void read()
{    f >> n >> m >> k;
     for (int i=1; i<=n; i++)
	 for (int j=1; j<=m; j++)
	     f >> v[i][j];
     if (k%m==0) I=k/m;
     else I=k/m+1;
     J=k-(I-1)*m;
     s[1]=k;
}

void initializare()
{    for (int i=0; i<=m+1; i++)
	 v[0][i]=v[n+1][i]=0;
     for (int j=0; j<=n+1; j++)
	 v[j][0]=v[j][m+1]=0;
}

void drum()
{    int u=1, p=1;
     c[u].x=I;
     c[u].y=J;
     c[u].ce=k;
     c[u].cn=0;
     c[u].k=1;
     v[1][1]=0;
     while (p<=u)
     {	   for (int k=1; k<4; k++)
	   {   xx=c[p].x+dx[k];
	       yy=c[p].y+dy[k];
	       cc=(xx-1)*m+yy;
	       if (v[xx][yy]!=0)
	       {  u++;
		  c[u].x=xx;
		  c[u].y=yy;
		  c[u].ce=cc;
		  c[u].cn=v[xx][yy];
		  v[xx][yy]=0;
	       }
	   }
	   p++;
     }
}

int verificare (int x)
{   for (int i=1; i<=cv; i++)
	if (s[i]==x) return 1;
    return 0;
}

void rezolvare()
{    int nr=1, ok=1;
     while (ok)
     {     ok=0;
	   for (int i=1; i<=n*m; i++)
	       if (c[i].k==0 && verificare(c[i].cn))
	       {  ok=1;
		  nr++;
		  c[i].k=1;
		  s[++cv]=c[i].ce;
	       }
     }
     g << nr;
}

int main()
{   read();
    initializare();
    drum();
    rezolvare();
    f.close();
    g.close();
    return 0;
}