Mysz w labiryncie - szkopuł

Question

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?

Answer 1

Nie mylisz może współrzędnych? np. nie powinno być rows[v.y - 1][v.x] zamiast rows[v.x][v.y - 1]?

Comments

Zgadza się. Poprawiłem kod w pytaniu, ale wystąpiły kolejne problemy. Opisałem w pytaniu.

---

Linia 24. Miało być chyba i < m

---

Racja. Ale błędy ciągle występują te same :/ Ogółem dostaję ostrzeżenie od VS "Buffer overrun while writing to 'visited'" w linii 64, i przy każdym ifie korzystającym z visited "Out of bound memory access", a w ostatnim ifie też "Read invalid data from 'visited'". Ale nie jestem pewny czy te ostrzeżenia są adekwatne, bo ify chyba sprawdzają, czy taka sytuacja występuje.

---

W linii 95 miało byc ev.y

---

Też prawda. I też ciągle te same błędy

---

Znalazłem kolejny błąd. W main zamiast rows.resize() do rozmiaru n powinno być do rozmiaru m. Po tym działaniu nie ma już "exit due to signal 11", jest tylko brak pamięci i czasu. Więc zamiast kolekcji visited zacząłem odwiedzone pozycje w rows oznaczać jako 'x', żeby zaoszczędzić pamięć. Nie sprawdzam też czy sąsiedzi nie są x-ami. Wale wszystkich sąsiadów na ślepo do kolejki i dodałem tylko jeden warunek, jeżeli obecny element z kolejki jest 'x' to po prostu przejdź do kolejnego elementu. Test zaliczony na 100% z max czasem. 0.17s :D