Question

Pe un lac se afla doua lebede, dar fiindca lacul este partial înghetat ele sunt separate de gheata.
Lacul are forma unui caroiaj dreptunghiular si consta din NxM patrate aranjate sub forma a N linii si M coloane. Unele dintre patrate sunt acoperite de gheata.
Lacul a început sa se dezghete treptat - într-o zi se dezgheata (se transforma în apa) toate patratele acoperite de gheata care ating apa (au o latura comuna cu un patrat reprezentând apa).
Figura urmatoare ilustreaza lacul din exemplu, apoi lacul dupa o zi, apoi lacul dupa doua zile:

Lebedele pot pluti numai pe apa, deplasându-se din patratul în care se afla într-un patrat învecinat pe orizontala sau verticala (nu si pe diagonala).

Cerinta
Scrieti un program care sa determine dupa câte zile se pot întâlni cele doua lebede.

Date de intrare
Fisierul de intrare lbd.in contine pe prima linie doua numere naturale N si M, separate prin spatiu, cu semnificatia din enunt. Pe fiecare dintre urmatoarele N linii se afla câte M caractere din multimea {'.','X','L'}. Caracterul '.' (punct) reprezinta un patrat cu apa; caracterul X (litera X majuscula) reprezinta un patrat acoprit de gheata; caracterul 'L' reprezinta un patrat în care se afla o lebada.

Date de iesire
Fisierul de iesire lbd.out va contine o singura linie pe care va fi scris un singur numar natural, reprezentând numarul de zile dupa care cele doua lebede se pot întâlni.

Restrictii
1<=N, M <=1500

Exemple

lbd.in lbd.out
8 17
...XXXXXX..XX.XXX
....XXXXXXXXX.XXX
...XXXXXXXXXXXX..
..XXXXX.LXXXXXX..
.XXXXXX..XXXXXX..
XXXXXXX...XXXX...
..XXXXX...XXX....
....XXXXX.XXXL...

Answer 1

Aceasta a fost cea mai bună problemă pe care am văzut-o pe Brainly de ceva timp. Aceasta este soluția mea:
#include <iostream> 
#include <fstream>
#include <string>
using namespace std;
bool path(int,int);
void newDay(void);
int nbx[] = {-1, 0, 1, 0}; // patrate vecine
int nby[] = {0, -1, 0, 1};
int N,M;
char l[1500][1500]; // lac ca se schimba
char t[1500][1500]; // lac a inceput zi.
int lx1=-1,ly1,lx2,ly2; // poziţie de lebede in lac
bool f2=false; // ajuns la 2° lebede?
int main()
{ int n=0, m=0;
string line;
ifstream myfile ("lbd.in");
if (myfile.is_open())
{
myfile>>N >> M; getline (myfile,line); // restul dispare
while ( getline (myfile,line) )
{
n++;
for (int i=0;i<M;i++){
l[n][i]=line.at(i);
if (l[n][i] == 'L'){
if (lx1 < 0){
lx1=n;
ly1=i;
} else {
lx2=n;
ly2=i;
} 
}
}
}
myfile.close();
}
int nd = 0; // n° zile
bool rd=false;
while (!rd){
for (int i=1;i<=N;i++) // copia lacului inițial
for (int j=0;j<M;j++)
t[i][j]=l[i][j];
rd = path(lx1,lx2); // desen route in lac. la inceput este lebede 1. rd: gasit lebede 2?
for (int i=1;i<=N;i++) // restabilirea lacului inițial
for (int j=0;j<M;j++)
l[i][j]=t[i][j];
if (!rd) {
nd++; // facem apa
newDay();
}
cout << nd;
}
return 0;
}
bool path(int x, int y){
if (x==lx2 && y==ly2) { // gasit
f2=true;
return true;
}
if (f2) return true; // gasit inainte
for (int i=0;i<4;i++){
if (x+nbx[i] >= 0 && x+nbx[i] <= N && y+nby[i] >= 0 && y+nby[i] <= M)
if (l[x+nbx[i]] [y + nby[i]] == '.' || l[x+nbx[i]] [y + nby[i]] == 'L') {
l [x+nbx[i]] [y + nby[i]] = 'R'; // desen route
if (path(x+nbx[i], y + nby[i])) 
return true;
}
}
return false;
}
void newDay(void){
for (int x=1;x<=N;x++){
for (int y=0;y<M;y++){
if (t[x] [y] == 'X'){ // t =  zi de ieri
for (int i=0;i<=3;i++){
if (x+nbx[i] > 0 && x+nbx[i] <= N && y+nby[i] >= 0 && y+nby[i] < M){
if (t[x+nbx[i]] [y + nby[i]] == '.' || t[x+nbx[i]] [y + nby[i]] == 'L') {
l[x] [y] = '.'; // l = situatie de azi
break;
}
}
}
}
}
}
return;
}