Cod sursa(job #580039)

Utilizator maritimCristian Lambru maritim Data 12 aprilie 2011 18:01:17
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include<stdio.h>
#include<malloc.h>

typedef struct _nod
{
	int x;
	int y;
	struct _nod *adr;
} nod;

int N;
int M;
int A[101][101];
int B[101][101];
short int L[9] = {0,-1,-1,0,1,1,1,0,-1};
short int C[9] = {0,0,1,1,1,0,-1,-1,-1};
short int rx;
short int ry;
short int jx;
short int jy;
int tmin = 200000;
short int X;
short int Y;


void citire(void)
{
	char c;
	FILE *f = fopen("rj.in","r");
	
	fscanf(f,"%d %d",&N,&M);
	fgetc(f);
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=M;j++)
		{
			c = fgetc(f);
			if(c == 'X')
				A[i][j] = -1;
			else if(c == 'R')
			{
				rx = i;
				ry = j;
			}
			else if(c == 'J')
			{
				
				jx = i;
				jy = j;
			}
		}
		fgetc(f);
	}
	
	fclose(f);
}

void add(nod*& Cf,int a,int b)
{
	nod *nou = (nod*)malloc(sizeof(nod));
	nou->x = a;
	nou->y = b;
	nou->adr = NULL;
	Cf->adr = nou;
	Cf = nou;
}

void lee(void)
{
	nod *Ci = (nod*)malloc(sizeof(nod));
	Ci->x = rx;
	Ci->y = ry;
	Ci->adr = NULL;
	nod *Cf = (nod*)malloc(sizeof(nod));
	Cf->x = jx;
	Cf->y = jy;
	Cf->adr = NULL;
	Ci->adr = Cf;
	A[rx][ry] = 1;
	A[jx][jy] = 1;
	B[rx][ry] = 1;
	B[jx][jy] = 2;
	while(Ci)
	{
		for(int i=1;i<=8;i++)
			if(Ci->x+L[i] && Ci->y+C[i] && Ci->x+L[i]<=N && Ci->y + C[i]<=M)
				if(!A[Ci->x+L[i]][Ci->y+C[i]])
				{
					add(Cf,Ci->x+L[i],Ci->y+C[i]);
					A[Ci->x+L[i]][Ci->y+C[i]] = A[Ci->x][Ci->y] + 1;
					B[Ci->x+L[i]][Ci->y+C[i]] = B[Ci->x][Ci->y];
				}
				else if(A[Ci->x+L[i]][Ci->y+C[i]] == A[Ci->x][Ci->y]+1 && B[Ci->x+L[i]][Ci->y+C[i]] != B[Ci->x][Ci->y])
				{
					if(tmin>A[Ci->x+L[i]][Ci->y+C[i]])
					{
						tmin = A[Ci->x+L[i]][Ci->y+C[i]];
						X = Ci->x + L[i];
						Y = Ci->y + C[i];
					}
					else if(tmin == A[Ci->x+L[i]][Ci->y+C[i]] && (X>Ci->x+L[i] || Y > Ci->y + C[i]))
					{
						X = Ci->x + L[i];
						Y = Ci->y + C[i];
					}
				}
		Ci = Ci->adr;
	}
}

int main()
{
	FILE *f = fopen("rj.out","w");
	
	citire();
	lee();
	fprintf(f,"%d %d %d",tmin,X,Y);
	
	fclose(f);
	return 0;
}