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;
}
