Perfekts labirints
Stāsts
Tavs draugs veido labirintus, un viņa mērķis ir izveidot perfektu labirintu. Tā kā šāda labirinta izveide nebūt nav vienkārša, viņš lūdz Tavu palīdzību.
Ir zināms, ka perfekts labirints atbilst šādiem nosacījumiem:
- Labirints ir rūtiņu laukums ar rindām (numurētas virzienā no augšas uz leju ar naturāliem skaitļiem pēc kārtas no līdz ) un kolonnām (numurētas no kreisās uz labo pusi ar naturāliem skaitļiem pēc kārtas no līdz ). Rūtiņa ar koordinātām atbilst rūtiņai laukuma kolonnā un rindā.
- Katra rūtiņa ir vai nu tukša (caur to var iziet) vai aizpildīta (caur to iziet nevar).
- Visas rūtiņas ar koordinātām , kur un abi ir nepāra skaitļi, ir tukšas.
- Visas rūtiņas ar koordinātām , kur un abi ir pāra skaitļi, ir aizpildītas.
- Labirintā divas tukšas blakus esošas rūtiņas sauc par savienotām, ja tām ir kopīga mala - t.i., viena koordināta sakrīt, bet otra - atšķiras par .
- Labirintā aizpildītās rūtiņas ir izvietotas tā, ka no katras tukšās rūtiņas eksistē tieši viens ceļš uz katru citu tukšo rūtiņu, izmantojot savienotās rūtiņas.
Tavs draugs labirintā ir izvēlējies rūtiņas, kurām noteikti jābūt aizpildītām.
Tavs uzdevums ir uzrakstīt datorprogrammu, kas izveido perfektu labirintu, ievērojot visus dotos nosacījumus un drauga izvēlētās aizpildītās rūtiņas, vai paziņo, ka šādu labirintu izveidot nav iespējams.
Ievaddati
Pirmajā rindā doti ar tukšumzīmēm atdalīti veseli skaitļi , , (, , ).
Tālāk seko rindas, kur katram () -tajā rindā ir dotas vienas Tava drauga izvēlētās aizpildītās rūtiņas koordinātas - divi ar tukšumzīmi atdalīti naturāli skaitļi un ( un ).
Izvaddati
Izvaddatu pirmajā rindā jāizvada VAR vai NEVAR atbilstoši tam, vai perfektu labirintu ir iespējams izveidot, vai nav.
Ja labirintu var izveidot, tad nākamajās rindās jāizvada perfekta labirinta apraksts, kur tukšās rūtiņas apzīmē ar ".", drauga izvēlētās aizpildītās rūtiņas - ar "@" un parējās aizpildītās rūtiņas - ar "#". Ja iespējams izveidot vairākus perfektus labirintus, jāizvada jebkura no tiem apraksts.
Piemēri
Ievaddati
4 5 2
4 2
2 4
Izvaddati
VAR
.#...
.#.@#
.....
.@.#.
Piezīme:
Tavs draugs vēlas izveidot perfektu labirintu, kur $N = 4, M = 5$, un ir izvēlējies divas aizpildītas rūtiņas $(4, 2)$ un $(2, 4)$. Sākuma konfigurācija:
Ievaddati
3 4 3
2 1
2 2
2 3
Izvaddati
NEVAR
Piezīme:
Tavs draugs vēlas izveidot perfektu labirintu, kur $N = 3, M = 4$, un ir izvēlējies trīs aizpildītas rūtiņas $(2, 1)$, $(2, 2)$ un $(2, 3)$. Sākuma konfigurācija:
Ievaddati
3 5 3
5 2
2 3
1 3
Izvaddati
NEVAR
Piezīme:
Tavs draugs vēlas izveidot perfektu labirintu, kur $N = 3, M = 5$, un ir izvēlējies trīs aizpildītas rūtiņas $(5, 2)$, $(2, 3)$ un $(1, 3)$. Sākuma konfigurācija:
Izpildes resursu ierobežojumi
Apakšuzdevumi un to vērtēšana
| # | Apakšuzdevuma apraksts | Punkti |
|---|---|---|
| 1. | Uzdevuma tekstā dotie testi | 2 |
| 2. | un | 6 |
| 3. | 8 | |
| 4. | 12 | |
| 5. | Lai tiktu izveidots labirints, nepieciešams aizpildīt vienu rūtiņu | 10 |
| 6. | Lai tiktu izveidots labirints, nepieciešams aizpildīt ne vairāk kā rūtiņas | 16 |
| 7. | Bez papildu ierobežojumiem | 46 |
1. apakšuzdevuma ievaddati
7 7 10
4 4
4 2
6 1
4 3
4 6
7 6
3 4
6 5
6 4
2 6
5 15 15
2 2
2 3
9 4
8 3
14 2
5 4
6 4
14 3
6 3
6 2
4 2
1 4
10 2
8 4
12 4
11 11 25
2 10
7 8
8 6
8 10
7 6
4 3
8 4
2 9
11 10
2 2
4 2
11 6
5 6
9 6
10 7
2 3
4 6
2 6
2 4
6 6
6 2
6 3
3 4
10 10
5 2
Perfekts labirints
Stāsts
Tavs draugs veido labirintus, un viņa mērķis ir izveidot perfektu labirintu. Tā kā šāda labirinta izveide nebūt nav vienkārša, viņš lūdz Tavu palīdzību.
Ir zināms, ka perfekts labirints atbilst šādiem nosacījumiem:
- Labirints ir rūtiņu laukums ar rindām (numurētas virzienā no augšas uz leju ar naturāliem skaitļiem pēc kārtas no līdz ) un kolonnām (numurētas no kreisās uz labo pusi ar naturāliem skaitļiem pēc kārtas no līdz ). Rūtiņa ar koordinātām atbilst rūtiņai laukuma kolonnā un rindā.
- Katra rūtiņa ir vai nu tukša (caur to var iziet) vai aizpildīta (caur to iziet nevar).
- Visas rūtiņas ar koordinātām , kur un abi ir nepāra skaitļi, ir tukšas.
- Visas rūtiņas ar koordinātām , kur un abi ir pāra skaitļi, ir aizpildītas.
- Labirintā divas tukšas blakus esošas rūtiņas sauc par savienotām, ja tām ir kopīga mala - t.i., viena koordināta sakrīt, bet otra - atšķiras par .
- Labirintā aizpildītās rūtiņas ir izvietotas tā, ka no katras tukšās rūtiņas eksistē tieši viens ceļš uz katru citu tukšo rūtiņu, izmantojot savienotās rūtiņas.
Tavs draugs labirintā ir izvēlējies rūtiņas, kurām noteikti jābūt aizpildītām.
Tavs uzdevums ir uzrakstīt datorprogrammu, kas izveido perfektu labirintu, ievērojot visus dotos nosacījumus un drauga izvēlētās aizpildītās rūtiņas, vai paziņo, ka šādu labirintu izveidot nav iespējams.
Ievaddati
Pirmajā rindā doti ar tukšumzīmēm atdalīti veseli skaitļi , , (, , ).
Tālāk seko rindas, kur katram () -tajā rindā ir dotas vienas Tava drauga izvēlētās aizpildītās rūtiņas koordinātas - divi ar tukšumzīmi atdalīti naturāli skaitļi un ( un ).
Izvaddati
Izvaddatu pirmajā rindā jāizvada VAR vai NEVAR atbilstoši tam, vai perfektu labirintu ir iespējams izveidot, vai nav.
Ja labirintu var izveidot, tad nākamajās rindās jāizvada perfekta labirinta apraksts, kur tukšās rūtiņas apzīmē ar ".", drauga izvēlētās aizpildītās rūtiņas - ar "@" un parējās aizpildītās rūtiņas - ar "#". Ja iespējams izveidot vairākus perfektus labirintus, jāizvada jebkura no tiem apraksts.
Piemēri
Ievaddati
4 5 2
4 2
2 4
Izvaddati
VAR
.#...
.#.@#
.....
.@.#.
Piezīme:
Tavs draugs vēlas izveidot perfektu labirintu, kur $N = 4, M = 5$, un ir izvēlējies divas aizpildītas rūtiņas $(4, 2)$ un $(2, 4)$. Sākuma konfigurācija:
Ievaddati
3 4 3
2 1
2 2
2 3
Izvaddati
NEVAR
Piezīme:
Tavs draugs vēlas izveidot perfektu labirintu, kur $N = 3, M = 4$, un ir izvēlējies trīs aizpildītas rūtiņas $(2, 1)$, $(2, 2)$ un $(2, 3)$. Sākuma konfigurācija:
Ievaddati
3 5 3
5 2
2 3
1 3
Izvaddati
NEVAR
Piezīme:
Tavs draugs vēlas izveidot perfektu labirintu, kur $N = 3, M = 5$, un ir izvēlējies trīs aizpildītas rūtiņas $(5, 2)$, $(2, 3)$ un $(1, 3)$. Sākuma konfigurācija:
Izpildes resursu ierobežojumi
Apakšuzdevumi un to vērtēšana
| # | Apakšuzdevuma apraksts | Punkti |
|---|---|---|
| 1. | Uzdevuma tekstā dotie testi | 2 |
| 2. | un | 6 |
| 3. | 8 | |
| 4. | 12 | |
| 5. | Lai tiktu izveidots labirints, nepieciešams aizpildīt vienu rūtiņu | 10 |
| 6. | Lai tiktu izveidots labirints, nepieciešams aizpildīt ne vairāk kā rūtiņas | 16 |
| 7. | Bez papildu ierobežojumiem | 46 |
1. apakšuzdevuma ievaddati
7 7 10
4 4
4 2
6 1
4 3
4 6
7 6
3 4
6 5
6 4
2 6
5 15 15
2 2
2 3
9 4
8 3
14 2
5 4
6 4
14 3
6 3
6 2
4 2
1 4
10 2
8 4
12 4
11 11 25
2 10
7 8
8 6
8 10
7 6
4 3
8 4
2 9
11 10
2 2
4 2
11 6
5 6
9 6
10 7
2 3
4 6
2 6
2 4
6 6
6 2
6 3
3 4
10 10
5 2