Pagini recente » Cod sursa (job #1918216) | Cod sursa (job #592553) | Cod sursa (job #2075992) | Cod sursa (job #1811183) | Cod sursa (job #2665792)
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
ifstream in ("rj.in");
ofstream out ("rj.out");
struct celula
{
int lin, col;
};
int matrixR [106][106], matrixJ [106][106], N, M;
int dx[8] = {0, 0, -1, -1, -1, 1, 1, 1};///vectori de coordonate pt. deplasarile pe celulele vecine
int dy[8] = {1, -1, -1, 1, 0, -1, 0, 1};
void Lee(celula x, int matrix[][106])
{
queue <celula> celule_speciale;
celule_speciale.push(x);
matrix[x.lin][x.col] = 1;
while (!celule_speciale.empty()) ///cat timp coada de celule speciale nu este goala calculam cu algoritmul lui Lee costul fiecarui
///drum de la o celula libera (.) (distanta minima) la una speciala si le adunam
{
celula nod = celule_speciale.front();
celule_speciale.pop();
//matrix[nod.lin][nod.col] = 1;
for (int vecin = 0; vecin <= 7; vecin++)
{
int lin = nod.lin + dy[vecin];
int col = nod.col + dx[vecin];
if (lin < N && col < M && lin >= 0 && col >= 0 && matrix[lin][col] == 0)
{ celula noua;
noua.lin = lin;
noua.col = col;
celule_speciale.push({lin,col});///adugam in coada noua celula pe care am parcurs-o
matrix[lin][col] = matrix[nod.lin][nod.col] + 1;///nu o mai vizitam o data
}
}
}
}
int main()
{
celula R,J;///locurile unde se afla ROMEO si JULIETA
char s[150];
in>> N >> M;
in.get();
for (int i = 0; i < N; i++)
{
in.getline(s,150);
for (int j = 0; j < M; j++)
{
if(s[j] == 'R')
{
matrixR[i][j] = matrixJ[i][j] = 0;
R.lin = i;
R.col = j;
}
else if(s[j] == 'J')
{
matrixR[i][j] = matrixJ[i][j] = 0;
J.lin = i;
J.col = j;
}
else if(s[j] == 'X')
{
matrixR[i][j] = matrixJ[i][j] = -1;
}
else if(s[j] == ' ')
{
matrixR[i][j] = matrixJ[i][j] = 0;
}
}
}
// for(int i = 0; i < N; i++)
// {
// for(int j = 0; j < M ; j++)
// {
// cout<<matrixR[i][j]<<" ";
//
// }
// cout<<"\n";
// }
// cout<<"yes\n";
//
Lee(R, matrixR);
//
// for(int i = 0; i < N; i++)
// {
// for(int j = 0; j < M ; j++)
// {
// cout<<matrixR[i][j]<<" ";
//
// }
// cout<<"\n";
// }
// cout<<"yes";
Lee(J, matrixJ);
// cout<<"yes";
int min = INT_MAX;
celula intalnire;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < M; ++j)
{
if (matrixR[i][j] > 0 && matrixR[i][j] == matrixJ[i][j] && matrixR[i][j] < min)
{
min = matrixR[i][j];
intalnire.lin = i;
intalnire.col = j;
}
}
}
out<<min<<" "<<intalnire.lin + 1 << " "<< intalnire.col + 1<<"\n";
return 0;
}