Nosaukums
Desants labirintā (desants)
Laika limits
1.00s
Atmiņas limits
32.0 MB
Grūtība
88%

Definīcija

Ir dots labirints, kas izskatās kā taisnstūris ar izmēriem M*N rūtiņas. Katra labirinta rūtiņa var būt gan tāda, caur kuru ir iespējams pārvietoties, gan tāda, caur kuru nav.
Vienība izsēdina desantnieku labirinta rūtiņā (M1,N1)(Šeit un turpmāk pirmais skaitlis - rindas numurs, otrais - kolonnas numurs).
Desantniekam nepieciešams nokļūt rūtiņā (M2,N2) pa īsāko iespējamo ceļu. Pārvietoties katrā solī drīkst tikai uz tādu brīvo rūtiņu, kurai ar pašreizējo ir kopīga mala.

Uzrakstiet programmu, kas atrod un izvada visus īsākos iespējamos ceļus no sākotnējās līdz beigu rūtiņai.


Ievaddatu raksturojums

Ievaddatu pirmajā rindā doti labirinta izmēri - naturāli skaitļi M(rindiņu skaits) un N(kolonnu skaits), kas atdalīti ar tukšumsimbolu. Zināms, ka 0 < M,N < 101.
Ievaddatu otrajā rindā dotas desantnieka sākotnējās rūtiņas koordinātas - M1 un N1 vērtības, kas atdalītas ar tukšumsimbolu.
Ievaddatu otrajā rindā dotas desantnieka beigu rūtiņas koordinātas - M2 un N2 vērtības, kas atdalītas ar tukšumsimbolu.
Ievaddatu nākošajās M rindās dots pa N simboliem - vienas labirinta rindas apraksts.
Ar simbolu # apzīmētās tās rūtiņas, caur kurām iziet nav iespējams, bet ar * tās, caur kurām pārvietošanās ir iespējama.


Izvaddatu raksturojums

Izvaddatu katrā rindā jāizvada visu īsāko ceļu apraksts, izvadot pa viena ceļa aprakstam katrā rindā.
Katra ceļa apraksts ir ciparu virkne, kur cipars «0» nozīmē «soli pa kreisi», «1» - soli uz augšu, «2» - soli pa labi, «3» - soli uz leju. Ciparu skaits skaitlī ir ceļa garums.
Ceļu apraksti jāizvada augošā secībā. Izvad faila izmērs nepārsniedz 1 megabaitu, un noteikti eksistē vismaz viens ceļš no sākotnējās uz beigu rūtiņu.


Piezīmes

Uzdevums ņemts no Baltkrievijas 2001. gada sacensībām.


Paraugdati

Stdin
2 2
1 1
2 2
**
**
Stdout
23
32

Stdin
3 3
1 1
3 2
***
##*
#**
Stdout
22330

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.