#2894
Barlog
Este anul 2019, dar Zmeul-Cel-Rău și Făt-Frumos luptă în continuare. Zmeul l-a prins pe Făt-Frumos şi l-a închis în una dintre camerele bârlogului său. Un bârlog de zmeu are forma unui tablou bidimensional, în care camerele sunt plasate sub forma a n
linii și m
coloane. Vom numerota liniile de la 1
la n
, iar coloanele de la 1
la m
, astfel că fiecare cameră poate fi identificată prin numărul liniei și al coloanei pe care se află.
Orice cameră are patru pereți și câte o ușă pe fiecare perete prin care poate comunica cu camerele învecinate. Mai exact, camera de pe linia i
și coloana j
poate comunica cu camerele (i-1,j)
, (i,j+1)
, (i+1,j)
, (i,j-1)
(desigur, dacă acestea există). Fiecare cameră are asociat un cod. Ușile din orice cameră se pot deschide cu o cartelă magnetică. Dacă codul camerei este un subșir al cuvântului memorat pe cartela magnetică, atunci ușile din camera respectivă se vor deschide folosind cartela. Ileana Cosânzeana a reușit să-i trimită lui Făt-Frumos o cartelă magnetică.
Scrieți un program care rezolvă următoarele două cerințe:
1. determină numărul de camere în care ar putea ajunge Făt-Frumos folosind cartela primită de la Ileana Cosânzeana;
2. determină numărul minim de camere prin care trece Făt-Frumos pentru a ieși din bârlogul zmeului (adică poate deschide ușa unei camere prin care ajunge în exteriorul bârlogului).
Olimpiada Municipală Iași, clasa a X-a
Problema | Barlog | Operații I/O |
barlog.in /barlog.out
|
---|---|---|---|
Limita timp | 0.1 secunde | Limita memorie |
Total: 4 MB
/
Stivă 2 MB
|
Id soluție | #49327440 | Utilizator | |
Fișier | barlog.cpp | Dimensiune | 3.26 KB |
Data încărcării | 26 Februarie 2024, 13:58 | Scor / rezultat | Eroare de compilare |
barlog.cpp: In function 'bool isSubsequence(const string&, const string&)': barlog.cpp:27:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] if (subIdx == sub.length()) { ^ barlog.cpp: In function 'int bfsMinRooms(int, int)': barlog.cpp:54:58: error: '__gnu_cxx::__alloc_traits<std::allocator<Room> >::value_type' has no member named 'neighbors' for (const Room& neighbor : barlog[row][col].neighbors) { ^ barlog.cpp: In function 'int main()': barlog.cpp:73:17: error: variable 'std::ifstream fin' has initializer but incomplete type ifstream fin("barlog.in"); ^ barlog.cpp:74:18: error: variable 'std::ofstream fout' has initializer but incomplete type ofstream fout("barlog.out"); ^ barlog.cpp:97:37: error: '__gnu_cxx::__alloc_traits<std::allocator<Room> >::value_type' has no member named 'neighbors' if (i > 0) barlog[i][j].neighbors.push_back({i - 1, j, barlog[i - 1][j].code}); ^ barlog.cpp:98:41: error: '__gnu_cxx::__alloc_traits<std::allocator<Room> >::value_type' has no member named 'neighbors' if (j < m - 1) barlog[i][j].neighbors.push_back({i, j + 1, barlog[i][j + 1].code}); ^ barlog.cpp:99:41: error: '__gnu_cxx::__alloc_traits<std::allocator<Room> >::value_type' has no member named 'neighbors' if (i < n - 1) barlog[i][j].neighbors.push_back({i + 1, j, barlog[i + 1][j].code}); ^ barlog.cpp:100:37: error: '__gnu_cxx::__alloc_traits<std::allocator<Room> >::value_type' has no member named 'neighbors' if (j > 0) barlog[i][j].neighbors.push_back({i, j - 1, barlog[i][j - 1].code}); ^
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
Problema Barlog face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:
Suma punctajelor acordate pe testele utilizate pentru verificare este 100. Astfel, soluția ta poate obține cel mult 100 de puncte, caz în care se poate considera corectă.