Shortest path between two points in a Matrix
Nu stiu de ce nu vrea sa afiseze....
Răspunsuri la întrebare
Salut!
Ai rezolvarea in C++ mai jos
#include <iostream>
#include <queue>
using namespace std;
int n, m, a[1001][1001], b[1001][1001];
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
bool inmat(int i, int j)
{
return i >= 1 && i <= n && j >= 1 && j <= m;
}
void lee(int i, int j)
{
queue<pair<int, int>> Q;
Q.push(make_pair(i, j));
b[i][j] = 1;
while (!Q.empty())
{
int x = Q.front().first;
int y = Q.front().second;
Q.pop();
for (int d = 0; d < 4; ++d)
{
int inou = dx[d] + x;
int jnou = dy[d] + y;
if (inmat(inou, jnou) && a[inou][jnou] == 0 && b[inou][jnou] == 0)
{
b[inou][jnou] = b[x][y] + 1;
Q.push(make_pair(inou, jnou));
}
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
cin >> a[i][j];
}
}
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
lee(x1, y1);
cout << b[x2][y2] - 1;
return 0;
}
- Explicatie:
- Folosim Algoritmul lui Lee
- Algoritmul lui Lee este folosit pentru determinarea iesirii dintr-un labirint sau in alte probleme similare cu aceasta.
- Pe langa cel mai scurt drum, acesta calculeaza si de cati pasi este nevoie pentru a ajunge la destinatie