Cod sursa(job #902474)

Utilizator Sonny2714Socoleanu Stefan Sonny2714 Data 1 martie 2013 14:29:18
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.63 kb
#include<fstream>
#define ff first
#define ss second
#include<queue>
#include <algorithm>
#define mkp make_pair
#define punct pair<int,int>
using namespace std;
punct startr,startj;
const int dx[]={0, 1, 0, -1, -1, 1, -1, 1};
const int dy[]={1, 0, -1, 0, -1, 1,  1,-1};
ofstream fout("rj.out");
int A[101][101],Dr[150][150],Dj[150][150],m,n,i;
void lee();
void citire()
{
    char x[255];
    int j;
    ifstream fin("rj.in");
    fin>>n>>m;
    fin.getline(x,255);
    for(i=1;i<=n;i++)
    {
        fin.getline(x,255);
        for(j=0;j<m;j++)
        {
        if(x[j]==' ')
            A[i][j]=0;
        else
            if(x[j]=='R')
            {
                startr.ff=i;
                startr.ss=j;

                A[i][j]=1;
            }
            else
                if(x[j]=='J')
                {
                    startj.ff=i;
                    startj.ss=j;
                    A[i][j]=1;
                }
                else
                    A[i][j]=-1;
        }
    }
}
void initializare();
void initializare()
{
   for(i=1;i<=n;i++)
    for(int j=0;j<m;j++)
    {
        Dr[i][j]=-1;
        Dj[i][j]=-1;
    }
   for (int i=0; i<=n+1; i++) A[i][-1]=A[i][m]=-1;
   for (int i=0; i<=m; i++) A[0][i]=A[n+1][i]=-1;
   Dr[startr.ff][startr.ss]=1;
   Dj[startj.ff][startj.ss]=1;
}
int afara(int linie, int col)
{
    return A[linie][col]!=-1;
}
void lee()
{
    initializare();
    queue<punct> R;
    queue<punct> J;
    punct now,now2;
    R.push(startr);
    while (R.empty()==false)
    {
        now=R.front();R.pop();
        for (i = 0; i < 8; ++i)
		{
			now2 = mkp(now.ff + dx[i], now.ss + dy[i]);
			if (afara(now2.ff,now2.ss)==1 && Dr[now2.ff][now2.ss]==-1&&A[now2.ff][now2.ss]==0)
			{
				Dr[now2.ff][now2.ss] = Dr[now.ff][now.ss] + 1;
				R.push(now2);
			}
		}
    }
    J.push(startj);
    while (J.empty()==false)
    {
        now=J.front();J.pop();
        for (i = 0; i < 8; ++i)
		{
			now2 = mkp(now.ff + dx[i], now.ss + dy[i]);
			if (afara(now2.ff,now2.ss)==1 && Dj[now2.ff][now2.ss]==-1&&A[now2.ff][now2.ss]==0)
			{
				Dj[now2.ff][now2.ss] = Dj[now.ff][now.ss] + 1;
				J.push(now2);
			}
		}
    }
}
int main ()
{
    citire();
    lee();
    int tmin=2000000,xmin,ymin,j,i;
    for(i=1;i<=n;i++)
        for(j=0;j<m;j++)
        {
          if(Dj[i][j]==Dr[i][j])
          {
              if (Dr[i][j]<tmin && Dr[i][j]!=-1)
              {
                  tmin=Dr[i][j];
                  xmin=i;
                  ymin=j;
              }

          }
        }
    fout<<tmin<<" "<<xmin<<" "<<ymin+1;
}