• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Mysz w labiryncie - szkopuł

Aruba Cloud - Virtual Private Server VPS
+1 głos
485 wizyt
pytanie zadane 7 czerwca 2023 w C i C++ przez Szyszka Gaduła (3,510 p.)
edycja 8 czerwca 2023 przez Szyszka

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?

1 odpowiedź

+1 głos
odpowiedź 7 czerwca 2023 przez Whistleroosh Maniak (57,400 p.)
wybrane 9 czerwca 2023 przez Szyszka
 
Najlepsza
Nie mylisz może współrzędnych? np. nie powinno być rows[v.y - 1][v.x] zamiast rows[v.x][v.y - 1]?
komentarz 8 czerwca 2023 przez Szyszka Gaduła (3,510 p.)
Zgadza się. Poprawiłem kod w pytaniu, ale wystąpiły kolejne problemy. Opisałem w pytaniu.
komentarz 8 czerwca 2023 przez Whistleroosh Maniak (57,400 p.)
Linia 24. Miało być chyba i < m
komentarz 8 czerwca 2023 przez Szyszka Gaduła (3,510 p.)
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.
komentarz 8 czerwca 2023 przez Whistleroosh Maniak (57,400 p.)
W linii 95 miało byc ev.y
komentarz 8 czerwca 2023 przez Szyszka Gaduła (3,510 p.)
Też prawda. I też ciągle te same błędy
komentarz 9 czerwca 2023 przez Szyszka Gaduła (3,510 p.)
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

Podobne pytania

+1 głos
2 odpowiedzi 878 wizyt
pytanie zadane 24 czerwca 2023 w C i C++ przez Szyszka Gaduła (3,510 p.)
0 głosów
1 odpowiedź 369 wizyt
pytanie zadane 30 maja 2023 w C i C++ przez Szyszka Gaduła (3,510 p.)
0 głosów
1 odpowiedź 531 wizyt
pytanie zadane 28 maja 2023 w C i C++ przez Szyszka Gaduła (3,510 p.)

93,335 zapytań

142,331 odpowiedzi

322,415 komentarzy

62,670 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj

Wprowadzenie do ITsec, tom 1 Wprowadzenie do ITsec, tom 2

Można już zamawiać dwa tomy książek o ITsec pt. "Wprowadzenie do bezpieczeństwa IT" - mamy dla Was kod: pasja (użyjcie go w koszyku), dzięki któremu uzyskamy aż 15% zniżki! Dziękujemy ekipie Sekuraka za fajny rabat dla naszej Społeczności!

...