Cod sursa(job #368352)

Utilizator dornescuvladVlad Eugen Dornescu dornescuvlad Data 24 noiembrie 2009 19:18:11
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.83 kb
#include<iostream>
#include<fstream>
#include<string.h>

using namespace std;

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

int i,j,k,m,n,minim=50000,minim2=50000,minim3=50000,a[105][105],o[105][105],o2[105][105],l,qi[105],qj[100],tmin,pozi,pozj,poz1,poz2,qi1[105],jnou,inou,qj1[105],poz3,poz4;
char x,s[105];


int first,last; 
 
 
int isempty() 
   {if (first == last)   
          return 1;  
	else return 0;} 



int main(){
	 f>>n>>m;
	 f.getline(s,100);
	  for(i=1;i<=n;i++)
		  {f.getline(s,105);
	       //cout<<s<<strlen(s)<<endl;
			  for(k=0;k<m;k++)
			    {if(s[k]=='R')
				   a[i][k+1]=10;
		         if(s[k]=='J')
				   a[i][k+1]=20;
				 if(s[k]==' ')
				   a[i][k+1]=1;
                 if(s[k]=='X')
				   a[i][k+1]=0;}
		  }
/*	for(i=1;i<=n;i++)
		{for(j=1;j<=m;j++)
			cout<<a[i][j]<<" ";
		cout<<endl;}
} */

for(i=0;i<=n+1;i++)
  {a[i][0]=-2; 
   a[i][m+1]=-2;}
  
for(i=0;i<=m+1;i++)
  {a[0][i]=-2;
   a[m+1][i]=-2;}
 
 /*for(i=0;i<=n+1;i++)
		{for(j=0;j<=m+1;j++)
			cout<<a[i][j]<<" ";
		cout<<endl;}}*/
		  


for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)
	 {if(a[i][j]==10)
	      {poz1=i;
	       poz2=j;}
      if(a[i][j]==20)
	      {poz3=i;
		   poz4=j;}}


for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)
		o[i][j]=n*n*n;

for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)
		o2[i][j]=n*n*n;	

qi[last]=poz1;
qj[last]=poz2;
qi1[last]=poz3;
qj1[last]=poz4;
o[poz1][poz2]=1;
o2[poz3][poz4]=1;
last=1;
while(!isempty())
{
	i=qi[first];
	j=qj[first];
    first++;
	inou = i+1;
	jnou = j;
		if (a[inou][jnou] == 1)
			if (o[inou][jnou] > 1+ o[i][j])
			{ 
				o[inou][jnou] = 1+ o[i][j];
				qi[last] = inou;
				qj[last] = jnou;
				last++;
			}
			
  	inou = i-1;
	jnou = j;
		if (a[inou][jnou] == 1)
			if (o[inou][jnou] > 1+ o[i][j])
			{ 
				o[inou][jnou] = 1+ o[i][j];
				qi[last] = inou;
				qj[last] = jnou;
				last++;
			}	  
	inou = i;
	jnou = j+1;
		if (a[inou][jnou] == 1)
			if (o[inou][jnou] > 1+ o[i][j])
			{ 
				o[inou][jnou] = 1+ o[i][j];
				qi[last] = inou;
				qj[last] = jnou;
				last++;
			} 	
	inou = i;
	jnou = j-1;
		if (a[inou][jnou] == 1)
			if (o[inou][jnou] > 1+ o[i][j])
			{ 
				o[inou][jnou] = 1+ o[i][j];
				qi[last] = inou;
				qj[last] = jnou;
				last++;
			}
	inou = i+1;
	jnou = j-1;
		if (a[inou][jnou] == 1)
			if (o[inou][jnou] > 1+ o[i][j])
			{ 
				o[inou][jnou] = 1+ o[i][j];
				qi[last] = inou;
				qj[last] = jnou;
				last++;
			}
	inou = i+1;
	jnou = j+1;
		if (a[inou][jnou] == 1)
			if (o[inou][jnou] > 1+ o[i][j])
			{ 
				o[inou][jnou] = 1+ o[i][j];
				qi[last] = inou;
				qj[last] = jnou;
				last++;
			}	
	inou = i-1;
	jnou = j+1;
		if (a[inou][jnou] == 1)
			if (o[inou][jnou] > 1+ o[i][j])
			{ 
				o[inou][jnou] = 1+ o[i][j];
				qi[last] = inou;
				qj[last] = jnou;
				last++;
			}	
	inou = i-1;
	jnou = j-1;
		if (a[inou][jnou] == 1)
			if (o[inou][jnou] > 1+ o[i][j])
			{ 
				o[inou][jnou] = 1+ o[i][j];
				qi[last] = inou;
				qj[last] = jnou;
				last++;
			}
}

    
	first=0;
    last=1;
	inou=0;
	jnou=0;
   

	while(!isempty())
{
	i=qi1[first];
	j=qj1[first];
    first++;
	inou = i+1;
	jnou = j;
		if (a[inou][jnou] == 1)
			if (o2[inou][jnou] > 1+ o2[i][j])
			{ 
				o2[inou][jnou] = 1+ o2[i][j];
				qi1[last] = inou;
				qj1[last] = jnou;
				last++;
			}
			
  	inou = i-1;
	jnou = j;
		if (a[inou][jnou] == 1)
			if (o2[inou][jnou] > 1+ o2[i][j])
			{ 
				o2[inou][jnou] = 1+ o2[i][j];
				qi1[last] = inou;
				qj1[last] = jnou;
				last++;
			}	  
	inou = i;
	jnou = j+1;
		if (a[inou][jnou] == 1)
			if (o2[inou][jnou] > 1+ o2[i][j])
			{ 
				o2[inou][jnou] = 1+ o2[i][j];
				qi1[last] = inou;
				qj1[last] = jnou;
				last++;
			} 	
	inou = i;
	jnou = j-1;
		if (a[inou][jnou] == 1)
			if (o2[inou][jnou] > 1+ o2[i][j])
			{ 
				o2[inou][jnou] = 1+ o2[i][j];
				qi1[last] = inou;
				qj1[last] = jnou;
				last++;
			}
	inou = i+1;
	jnou = j-1;
		if (a[inou][jnou] == 1)
			if (o2[inou][jnou] > 1+ o2[i][j])
			{ 
				o2[inou][jnou] = 1+ o2[i][j];
				qi1[last] = inou;
				qj1[last] = jnou;
				last++;
			}
	inou = i+1;
	jnou = j+1;
		if (a[inou][jnou] == 1)
			if (o2[inou][jnou] > 1+ o2[i][j])
			{ 
				o2[inou][jnou] = 1+ o2[i][j];
				qi1[last] = inou;
				qj1[last] = jnou;
				last++;
			}	
			
	inou = i-1;
	jnou = j+1;
		if (a[inou][jnou] == 1)
			if (o2[inou][jnou] > 1+ o2[i][j])
			{ 
				o2[inou][jnou] = 1+ o2[i][j];
				qi1[last] = inou;
				qj1[last] = jnou;
				last++;
			}	
	inou = i-1;
	jnou = j-1;
		if (a[inou][jnou] == 1)
			if (o2[inou][jnou] > 1+ o2[i][j])
			{ 
				o2[inou][jnou] = 1+ o2[i][j];
				qi1[last] = inou;
				qj1[last] = jnou;
				last++;
			}}

    /*	
	for(i=1;i<=n;i++)
		{for(j=1;j<=m;j++)
			 if(o[i][j]==n*n*n)
		         o[i][j]=-1;}

	for(i=1;i<=n;i++)
		{for(j=1;j<=m;j++)			
		    if(o2[i][j]==n*n*n)
			    o2[i][j]=-1;}
	
	for(i=1;i<=n;i++)
		{for(j=1;j<=m;j++)
			cout<<o[i][j]<<" ";
		cout<<endl;}
    cout<<endl;
	for(i=1;i<=n;i++)
        {for(j=1;j<=m;j++)
            cout<<o2[i][j]<<" ";
		cout<<endl;}
	cout<<endl;
     for(i=1;i<=n;i++)
        {for(j=1;j<=m;j++)
            cout<<a[i][j]<<" ";
		cout<<endl;}
	*/
		
		
		
    for(i=1;i<=n;i++)
       {for(j=1;j<=m;j++)
          if(o[i][j]!=-1 && o2[i][j]!=-1 && o[i][j]==o2[i][j])
			   
			     if(o[i][j]+o2[i][j]<minim)
				    {if(i<minim2)	 
                        {minim2=i;
						 minim=o[i][j]+o2[i][j];				  
	                     pozi=i;
						 pozj=j;
						 tmin=o2[i][j];}
					 if(i==minim2)	
					   if(j<minim3)
					    {minim3=j;
					     minim=o[i][j]+o2[i][j];				  
	                     pozi=i;
						 pozj=j;
						 tmin=o2[i][j];}}}
					     
           	   
    g<<tmin<<" "<<pozi<<" "<<pozj<<" ";			 
	return 0;}