Cod sursa(job #675791)

Utilizator PatrikStepan Patrik Patrik Data 8 februarie 2012 10:38:56
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
	#include<stdio.h>
	#include<string.h>
	FILE *f , *g ;
	int n , m  , a[101][101] , b[101][101] ,x1,x2,y1,y2 , x[100001] , y[100001] , sol1 , sol2 ;
	long min;
	char c ,s[120];
	int dx[] = {0,-1,-1,0,1,1,1,0,-1} , dy[] = {0,0,1,1,1,0,-1,-1,-1};
	
	void citire();
	void solve();
	void tipar();
	
	int main()
	{
		citire();
		solve();
		tipar();
		return 0;
	}
	
	void citire()
	{
		f=fopen("rj.in" , "r" );
		fscanf(f , "%d%d\n" , &n , &m );
		for(int i = 1 ; i<= n ; ++i )
		{
			fgets(s,120,f);
			for(int j = 0 ; j < m ; ++j )
			{
				if(s[j] != ' ')
					a[i][j+1] = b[i][j+1] = 1;
				if(s[j] == 'R')
				{
					x1 = i;y1 = j+1;
				}
				if(s[j] == 'J')
				{
					x2 = i;y2 = j+1;
				}
			}
		}
			fclose(f);
	}
	
	void solve()
	{
		sol1 = n;sol2 = m;
		x[1] = x1;y[1] = y1;
		int ls , ld , k , p = 1 ;
		ls = ld = k = 1;
		while(ls <= ld )
		{
			p++;
			for(int i = ls ; i<= ld ; ++i )
			{
				for(int j = 1 ; j <= 8 ; ++j )
				{
					if(x[i]+dx[j] && x[i]+dx[j] <= n && y[i]+dy[j] && y[i]+dy[j] <= m && a[x[i]+dx[j]][y[i]+dy[j]] == 0)
					{
						x[++k] = x[i]+dx[j];
						y[k] = y[i]+dy[j];
						a[x[i]+dx[j]][y[i]+dy[j]] = p;
					}
				}
			}
			ls = ld+1;
			ld = k;
		}
		x[1] = x2 ; y[1] = y2;
		ls = ld = k = 1;
		p = 1;
		bool sw = 1;
		while(ls <= ld && sw)
		{
			p++;
			for(int i = ls ; i<= ld ; ++i )
			{
				for(int j = 1 ; j <= 8 ; ++j )
				{
					if(x[i]+dx[j] && x[i]+dx[j] <= n && y[i]+dy[j] && y[i]+dy[j] <= m && b[x[i]+dx[j]][y[i]+dy[j]] == 0)
					{
						x[++k] = x[i]+dx[j];
						y[k] = y[i]+dy[j];
						b[x[i]+dx[j]][y[i]+dy[j]] = p;
						if(	a[x[i]+dx[j]][y[i]+dy[j]] == p)
						{
							sw = 0;
							min = p;
							if(sol1 >x[i]+dx[j] || (sol1 == x[i]+dx[j] && sol2 >y[i]+dy[j]) )
							{
								sol1 = x[i]+dx[j];
								sol2 = y[i] + dy[j];
							}
						}
					}
				}
			}
			ls = ld+1;
			ld = k;
		}
	}
	
	void tipar()
	{
		g=fopen("rj.out" , "w");
		/*for(int i = 1 ; i<= n ; ++i )
		{
			for(int j = 1 ; j <= m ; ++j )
				fprintf(g , "%d " , a[i][j] );
			fprintf(g , "\n");
		}*/
		fprintf(g , "%ld %d %d" , min , sol1 , sol2 );
		fclose(g);
	}