[C++, programare dinamică] Problemă cu algoritmul lui Lee (a)

Introducere în problema labirintului aici.

Enunț

a) Considerăm că o persoană pornește din (1, 1) și alta din (N, N). Cele două persoane se mișcă exact în același timp. Scrieți un program care determină coordonatele spre care acestea ar trebui să se îndrepte pentru a se întâlni cât mai rapid.

Rezolvare

#include <fstream>
#include <queue>
#include <utility>

using namespace std;

const int maxn = 101;
const int inf = 1 << 30;
const int dx[] = { 1, 0, -1, 0 };
const int dy[] = { 0, 1, 0, -1 };

void citire(bool A[maxn][maxn], int &N)
{
 ifstream in("ex-a.in");
 in >> N;
 for (int i = 1; i <= N; ++i)
 {
  for (int j = 1; j <= N; ++j)
  {
   in >> A[i][j];
  }
 }
 in.close();
}

bool valid(int N, int x, int y)
{
 return x >= 1 && y >= 1 &&
  x <= N && y <= N;
}

void Lee_optim(bool A[maxn][maxn], int N,
 int x, int y,
 int D[maxn][maxn])
{
 queue<pair<int, int>> Q;
 Q.push(make_pair(x, y));

 while (!Q.empty())
 {
  pair<int, int> poz = Q.front();
  Q.pop();

  for (int i = 0; i < 4; ++i)
  {
   int newx = poz.first + dx[i];
   int newy = poz.second + dy[i];

   if (valid(N, newx, newy))
   {
    if (!A[newx][newy] &&
     D[newx][newy] > D[poz.first][poz.second] + 1)
    {
     D[newx][newy] = D[poz.first][poz.second] + 1;
     Q.push(make_pair(newx, newy));
    }
   }
  }
 }
}

void init(int D[maxn][maxn], int N, int x, int y)
{
 for (int i = 1; i <= N; ++i)
 {
  for (int j = 1; j <= N; ++j)
  {
   D[i][j] = inf;
  }
 }
 D[x][y] = 0;
}

int main()
{
 int N;
 bool A[maxn][maxn];
 int D1[maxn][maxn];
 int D2[maxn][maxn];

 citire(A, N);

 init(D1, N, 1, 1);
 Lee_optim(A, N, 1, 1, D1);

 init(D2, N, N, N);
 Lee_optim(A, N, N, N, D2);

 int max = -inf;
 int x = -1, y = -1;
 for (int i = 1; i <= N; ++i)
 {
  for (int j = 1; j <= N; ++j)
  {
   if (!A[i][j] &&
    D1[i][j] == D2[i][j])
   {
    if (D1[i][j] > max)
    {
     max = D1[i][j];
     x = i;
     y = j;
    }
   }
  }
 }

 ofstream out("ex-a.out");
 out << x << ' ' << y << endl;
 out.close();

 return 0;
}

Explicație

Fișierul de intrare este ex-a.in și cel de ieșire este ex-a.out.

Se folosesc două matrice D construite din matricea de intrare A, se aplică același algoritm pt. ambele (algoritmul lui Lee) dar din puncte de pornire diferite (cele specificate în enunț). Se lasă algoritmul să ruleze pe toată suprafața matricelor. Se compară fiecare celulă din matricea D1 cu cea din matricea D2 de pe aceeași poziție, și dacă au aceeași valoare, se calculează treptat poziția valorii minime care se găsește în ambele matrice D pe aceeași poziție. Se ignoră valorile de 1 care reprezintă ziduri.

Niciun comentariu:

Trimiteți un comentariu