Cod sursa(job #1372337)

Utilizator ioncorinamariaIon Corina ioncorinamaria Data 4 martie 2015 12:55:56
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include<iostream>
#include<fstream>
#include<string.h>
#include<queue>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int i,n,m,j,y,x,xx,yy,xf,yf,a[105][105],b[105][105],mini=3200000,X,Y;
queue<int> Qx;
queue<int> Qy;
int main()
{

	char c[105];
	f>>n>>m;
	for(i=1;i<=n;i++)
        {f.get();f.get(c,105);
         for(j=1;j<=m;j++)
            if(c[j-1]=='X')a[i][j]=b[i][j]=-1;
                    else if(c[j-1]=='R'){x=i;y=j;}
                                else if(c[j-1]=='J'){xf=i;yf=j;}
        
        }
	for(i=0;i<=m+1;i++){a[0][i]=-1;
					   a[n+1][i]=-1;
					   b[0][i]=-1;
					   b[n+1][i]=-1;}
	for(i=0;i<=n+1;i++){a[i][0]=-1;
					   a[i][m+1]=-1;
					   b[i][0]=-1;
					   b[i][m+1]=-1;}
    //lee1
    Qx.push(x);Qy.push(y);
    while(Qx.empty()!=1)
		{xx=Qx.front();yy=Qy.front();
		  if(a[xx-1][yy]==0||a[xx-1][yy]>a[xx][yy]+1){a[xx-1][yy]=a[xx][yy]+1;
														Qx.push(xx-1);
														Qy.push(yy);}
		  if(a[xx+1][yy]==0||a[xx+1][yy]>a[xx][yy]+1){a[xx+1][yy]=a[xx][yy]+1;
														Qx.push(xx+1);
														Qy.push(yy);}
		  if(a[xx][yy-1]==0||a[xx][yy-1]>a[xx][yy]+1){a[xx][yy-1]=a[xx][yy]+1;
														Qx.push(xx);
														Qy.push(yy-1);}
		  if(a[xx][yy+1]==0||a[xx][yy+1]>a[xx][yy]+1){a[xx][yy+1]=a[xx][yy]+1;
														Qx.push(xx);
														Qy.push(yy+1);}
		Qx.pop();Qy.pop();
		}
    a[x][y]=0;
	//lee2
    Qx.push(xf);Qy.push(yf);
    while(Qx.empty()!=1)
		{xx=Qx.front();yy=Qy.front();
		  if(b[xx-1][yy]==0||b[xx-1][yy]>b[xx][yy]+1){b[xx-1][yy]=b[xx][yy]+1;
														Qx.push(xx-1);
														Qy.push(yy);}
		  if(b[xx+1][yy]==0||b[xx+1][yy]>b[xx][yy]+1){b[xx+1][yy]=b[xx][yy]+1;
														Qx.push(xx+1);
														Qy.push(yy);}
		  if(b[xx][yy-1]==0||b[xx][yy-1]>b[xx][yy]+1){b[xx][yy-1]=b[xx][yy]+1;
														Qx.push(xx);
														Qy.push(yy-1);}
		  if(b[xx][yy+1]==0||b[xx][yy+1]>b[xx][yy]+1){b[xx][yy+1]=b[xx][yy]+1;
														Qx.push(xx);
														Qy.push(yy+1);}
		Qx.pop();Qy.pop();
		}
    b[xf][yf]=0;

	for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
             if (a[i][j]>0&&a[i][j]==b[i][j])
                 if(a[i][j]<mini){mini=a[i][j];
                                 X=i;Y=j;}
	g<<mini<<' '<<X<<' '<<Y<<'\n';
    f.close();
    g.close();
    return 0;}