Witam,
Ostatnio zacząłem uczyć się grafów i chciałem zrobić parę zadanek. I zaciąłem się na myszach w labiryncie https://szkopul.edu.pl/problemset/problem/Wm6JcGbhvM2t4Hfam8UuuXLl/site/?key=statement
Chciałem zrobić coś ala BFS ale przy możliwych ruchach północ, południe, wschód i zachód. Oto mój kod:
#include <iostream>
#include <vector>
#include <queue>
struct Vector2D {
public:
Vector2D(uint32_t x, uint32_t y) : x(x), y(y)
{
}
uint32_t x;
uint32_t y;
bool operator ==(const Vector2D& v2) const {
return x == v2.x && y == v2.y;
}
};
bool can_escape(const std::vector<std::string>& rows, const Vector2D& sv, const Vector2D& ev, const uint32_t& n, const uint32_t& m) {
std::queue<Vector2D> vectors;
vectors.push(sv);
bool** visited = new bool* [m];
for (uint32_t i = 0; i < n; i++)
visited[i] = new bool[n];
for (uint32_t i = 0; i < m; i++)
for (uint32_t j = 0; j < n; j++)
visited[i][j] = false;
while (!vectors.empty()) {
Vector2D v = vectors.front();
vectors.pop();
if (v == ev) {
delete[] visited;
return true;
}
if (v.y > 0 && !visited[v.y - 1][v.x]) {
char top_adj = rows[v.y - 1][v.x];
if (top_adj != 'x')
vectors.push(Vector2D(v.x, v.y - 1));
}
if (v.y < m - 1 && !visited[v.y + 1][v.x]) {
char bottom_adj = rows[v.y + 1][v.x];
if (bottom_adj != 'x')
vectors.push(Vector2D(v.x, v.y + 1));
}
if (v.x > 0 && !visited[v.y][v.x - 1]) {
char left_adj = rows[v.y][v.x - 1];
if (left_adj != 'x')
vectors.push(Vector2D(v.x - 1, v.y));
}
if (v.x < n - 1 && !visited[v.y][v.x + 1]) {
char right_adj = rows[v.y][v.x + 1];
if (right_adj != 'x')
vectors.push(Vector2D(v.x + 1, v.y));
}
visited[v.y][v.x] = true;
}
delete[] visited;
return false;
}
int main()
{
uint32_t n, m;
std::cin >> n >> m;
std::vector<std::string> rows;
rows.resize(n);
Vector2D sv(0, 0);
Vector2D ev(0, 0);
for (uint32_t i = 0; i < m; i++) {
std::cin >> rows[i];
size_t sv_x = rows[i].find("o");
if (sv_x != std::string::npos) {
sv.x = sv_x;
sv.y = i;
}
size_t ev_x = rows[i].find("w");
if (ev_x != std::string::npos) {
ev.x = ev_x;
sv.y = i;
}
}
bool escaped = can_escape(rows, sv, ev, n, m);
if (escaped) std::cout << "TAK";
else std::cout << "NIE";
return 0;
}
Rozumiem, że gdybym cały input zamienił od razu na np. adjacency list to byłoby to prostsze rozwiązanie, ale taki sposób wydaje mi się bardziej ciekawy. Jednak gdy testuje ten kod to dostaje zazwyczaj process exited due to signal 11 i błędy o przekroczeniu limitu pamięci. Jak mogę zredukować zużycie pamięci i naprawić ten nic niemówiący mi błąd?

