Cod sursa(job #2684212)

Utilizator bibiancapitu2004Pitu Bianca bibiancapitu2004 Data 13 decembrie 2020 10:40:40
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <fstream>
using namespace std;

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

const int MAXN = 100;
const int MAXM = 100;
int main()
{

struct Celula
{
	int l, c;
};
int M , N, linie_s_j,coloana_s_j,linie_s_r ,coloana_s_r ,x , y;
in >> N >> M;

Celula coada[MAXN * MAXM + 5];
int st, dr;
char matrice[MAXN + 1][MAXM + 1];
int distanta_r[MAXN + 1][MAXM + 1] , distanta_j[MAXN + 1][MAXM + 1];
Celula parinte[MAXN + 1][MAXM + 1];

for(int i = 1;i <= N;i ++)
{
    for(int j = 1;j <= M;j ++)
    {
        in >> matrice[i][j];
        if(matrice[i][j] == 'R')
        {
            linie_s_r = i;
            coloana_s_r = j;
        }
        else if(matrice[i][j] == 'J')
        {
            linie_s_j = i;
            coloana_s_j = j;
        }
    }
}

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

int x_vecin , y_vecin ;
Celula start;


start.l = linie_s_r;
start.c = coloana_s_r;
coada[1] = start;
st = dr = 1;
distanta_r[linie_s_r][coloana_s_r] = 1;

while (st <= dr)
{
	Celula curent = coada[st];
	int x = curent.l;
	int y = curent.c;

	for (int d = 0; d < 4; ++d)
    {
		int x_vecin = x + dx[d];
		int y_vecin = y + dy[d];
		if (1 <= x_vecin && x_vecin <= N && 1 <= y_vecin && y_vecin <= M && matrice[x_vecin][y_vecin] != 'X'  && distanta_r[x_vecin][y_vecin] == 0)
		{
	      distanta_r[x_vecin][y_vecin] = distanta_r[x][y] + 1;
	      parinte[x_vecin][y_vecin] = curent;
	      Celula vecin;
          vecin.l = x_vecin, vecin.c=y_vecin;
	      dr++;
          coada[dr] = vecin;
        }
    }
	st++; //il scoatem pe curent din coada
}

start.l = linie_s_j;
start.c = coloana_s_j;
coada[1] = start;
st = dr = 1;
distanta_j[linie_s_r][coloana_s_j] = 1;

while (st <= dr)
{
	Celula curent = coada[st];
	int x = curent.l;
	int y = curent.c;

	for (int d = 0; d < 4; ++d)
    {
		int x_vecin = x + dx[d];
		int y_vecin = y + dy[d];
		if (1 <= x_vecin && x_vecin <= N && 1 <= y_vecin && y_vecin <= M && matrice[x_vecin][y_vecin] != 'X'  && distanta_j[x_vecin][y_vecin] == 0)
		{
	      distanta_j[x_vecin][y_vecin] = distanta_j[x][y] + 1;
	      parinte[x_vecin][y_vecin] = curent;
	      Celula vecin;
          vecin.l = x_vecin, vecin.c=y_vecin;
	      dr++;
          coada[dr] = vecin;
        }
    }
	st++; //il scoatem pe curent din coada
}

int timp = 1000000, lcelula, ccelula;
for(int i = 1;i <= N;i ++)
    for(int j = 1;j <= M;j ++)
if(distanta_r[i][j] == distanta_j[i][j] && distanta_r[i][j] < timp)
    {
        timp = distanta_r[i][j];
        lcelula = i;
        ccelula = j;
    }


    out << timp - 1 <<" "<< lcelula <<" "<< ccelula;
    return 0;
}