Cod sursa(job #1169866)

Utilizator andreey_047Andrei Maxim andreey_047 Data 12 aprilie 2014 11:10:48
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <fstream>

using namespace std;

char a[103][103];
int b[103][103],c[103][103], m, n,k,xr,yr,xj,yj,ii,jj,minim;

    struct coord
{
	int x, y, c;
};
coord q[10009],p[10009];

int dx[] = {-1, 0, 1,  0, -1,1,-1,1};
int dy[] = { 0, 1, 0, -1, -1,1,1,-1};

void Citire()
{
    ifstream fin("rj.in");
    fin >> n >> m;
    fin.get();
    for (int i = 1; i <= n; i++)
        fin.getline((a[i] + 1), 101);
    fin.close();
}
void Bordare()
{
    int i,j;
    for(i = 0;i<=n+1;i++)
      a[i][0] = a[i][m+1] = 'X';

     for(i = 0;i<=m+1;i++)
      a[0][i] = a[n+1][i] = 'X';

       for(i=1;i<=n;i++)
      {
          for(j=1;j<=m;j++)
           {
               if (a[i][j] == 'R') {xr=i; yr=j;}
               if (a[i][j] == 'J') {xj=i; yj=j;}
           }
      }

}
 void Afisare()
 {  int i,j;
     ofstream fout("rj.out");
    fout<<minim<<" "<<ii<<" "<<jj<<"\n";
 }
 void Inserare(coord w)
{
	int i;
	i = k;
	while (i >= 0 && q[i].c < w.c)
	{
		q[i+1] = q[i];
		i--;
	}
	q[i+1] = w;
	k++;
}

void Lee1()
{
	int j;
	coord w, w1;
	q[0].x = xr;
	q[0].y = yr;
	q[0].c = 1;
	b[xr][yr] = 1;
	k = 0;
	while (k >= 0)
	{
		w = q[k];
		k--;

		for (j = 0; j < 8; j++)
		{
			w1.x = w.x + dx[j];
			w1.y = w.y + dy[j];

			if ( (a[w1.x][w1.y] == ' ' || a[w1.x][w1.y] == 'R'|| a[w1.x][w1.y] == 'J' ) && (b[w1.x][w1.y] == 0 || b[w1.x][w1.y] > b[w.x][w.y] + 1) )
			{
				w1.c = b[w1.x][w1.y] = b[w.x][w.y] + 1;
				Inserare(w1);
			}
		}
	}
}
    void Lee2()
{
	int j,i;
	coord w, w1;
    for(i=0;i<10003;i++)
     q[i].x = q[i].y = q[i].c=0;

	q[0].x = xj;
	q[0].y = yj;
	q[0].c = 1;
	c[xj][yj] = 1;
	k = 0;
	while (k >= 0)
	{
		w = q[k];
		k--;

		for (j = 0; j < 8; j++)
		{
			w1.x = w.x + dx[j];
			w1.y = w.y + dy[j];

			if ( (a[w1.x][w1.y] == ' ' || a[w1.x][w1.y] == 'R'|| a[w1.x][w1.y] == 'J' ) && (c[w1.x][w1.y] == 0 || c[w1.x][w1.y] > c[w.x][w.y] + 1) )
			{
				w1.c = c[w1.x][w1.y] = c[w.x][w.y] + 1;
				Inserare(w1);
			}
		}
	}
}
void Done()
{ int i,j;
    minim = 999999999;
    for(i = 1;i<=n;i++)
      for(j = 1;j<=m;j++)
       if(b[i][j] == c[i][j] && b[i][j]<minim&&b[i][j] != 0) {minim = b[i][j]; ii = i;jj=j;}
}

int main()
{
    Citire();
    Bordare();
    Lee1();
    Lee2();
    Done();
    Afisare();
    return 0;
}