Cod sursa(job #1277552)

Utilizator dnprxDan Pracsiu dnprx Data 27 noiembrie 2014 20:18:33
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <fstream>
//#include <iostream>
#include <queue>

using namespace std;
char a[115][115];
int L, C, b[115][115], c[115][115], xr, yr, xj, yj;
struct coord
{
    int x, y, pas;
};
int dx[] = {-1,1, 0,0,-1,1,-1, 1};
int dy[] = { 0,0,-1,1,-1,1, 1,-1};

void Citire()
{
	int i, j;
	ifstream fin("rj.in");
	fin >> L >> C;
	fin.get();
	for (i = 1; i <= L; i++)
	     fin.getline(a[i]+1, 105);
	fin.close();
	for (i = 1; i <= L; i++)
		for (j = 1; j <= C; j++)
			if (a[i][j]== 'R')
             {xr=i;yr=j;}
            else if (a[i][j]=='J')
             {xj=i;yj=j;}
    fin.close();
    //cout << xr << " -- " << yr << "\n";
}

void Bordare()
{
	int i;
	for (i=0;i<=L+1;i++)
		a[i][0]=a[i][C+1]='X';
	for (i=0;i<=C+1;i++)
		a[0][i]=a[L+1][i]='X';
}

void LeeR()
{
    int k;
	queue <coord> q;
	coord w, w1;
	w.x=xr;
	w.y=yr;
	w.pas = 1;
	b[xr][yr] = 1;
	q.push(w);
    while (!q.empty())
    {
        w=q.front();
        q.pop();
        for (k = 0 ; k < 8; k++)
        {
            // nord
            w1.x = w.x + dx[k];
            w1.y = w.y + dy[k];
            w1.pas = w.pas + 1;
            if ((a[w1.x][w1.y]!='X') && ( b[w1.x][w1.y] == 0 || b[w1.x][w1.y] > w1.pas))
            {
                b[w1.x][w1.y]=w1.pas;
                q.push(w1);
            }
        }
    }
}

void LeeJ()
{
    int k;
	queue <coord> q;
	coord w, w1;
	w.x=xj;
	w.y=yj;
	w.pas = 1;
	c[xj][yj] = 1;
	q.push(w);
    while (!q.empty())
    {
        w=q.front();
        q.pop();
        for (k = 0 ; k < 8; k++)
        {
            // nord
            w1.x = w.x + dx[k];
            w1.y = w.y + dy[k];
            w1.pas = w.pas + 1;
            if ((a[w1.x][w1.y]!='X') && ( c[w1.x][w1.y] == 0 || c[w1.x][w1.y] > w1.pas))
            {
                c[w1.x][w1.y]=w1.pas;
                q.push(w1);
            }
        }
    }
}

void Afisare()
{
	ofstream fout ("rj.out");
	int i,j, xf, yf, minim = 1000000000;
	xf = yf = 0;
    for (i=1;i<=L;i++)
        for (j=1;j<=C;j++)
                if (b[i][j] == c[i][j] && b[i][j] != 0 && minim > b[i][j])
                {
                    minim=b[i][j];
                    xf=i;
                    yf=j;
                }
    fout << minim << " " << xf << " " << yf <<"\n";
    /*
    for (i=1;i<=L;i++)
	{
	    for (j=1;j<=C;j++)
	    {
	        fout.width(4);
	        fout<<b[i][j];
	    }

        fout<<"\n";
    }
    fout<<"\n";
    for (i=1;i<=L;i++)
	{
	    for (j=1;j<=C;j++)
	    {
	        fout.width(4);
	        fout<<c[i][j];
	    }

        fout<<"\n";
    }
*/
    fout.close();
}


int main()
{
	Citire();
	Bordare();
	LeeR();
	LeeJ();
	Afisare();
	return 0;
}