Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem S. 34. (March 2008)

S. 34. Once upon a time, a king of a distant country decided to wed his daughter. He commanded his architect to build a labyrinth full of dragons. ``A knight is allowed to engage my daughter only if he enters the labyrinth, then leaves at any other exit,'' said the king. Moreover, the king wants to be sure that if a knight gets through the labyrinth alive (using any exit), he cuts off at least a given number of dragon heads.

Your program should verify whether a given labyrinth has this property. The plan of the labyrinth is read from a file, and the output is also written in a file. The names of these files are given as the first and second command line arguments to your program.

The first line of the input contains the width W and height H of the plan of the maze (separated by spaces, with 3\leW,H\le100), further the minimal number of dragon heads F to cut off. Each of the following H lines then contain W characters, which can be

a space, if the given square is part of a corridor, and all four neighbouring squares can be reached

J, B, F and L, if the given square is a corridor with a gate, so a neighbouring square to the J (=east), B (=west), F (=north) or L (=south) direction can not be reached

*, if the given square is a wall

a digit N (from 1 to 9), if the given square is a corridor-square with an N-headed dragon lurking on it, and that dragon should be eliminated.

Entrances of the labyrinth are the corridor-squares on the border of the labyrinth. They contain no dragons and have at least one adjacent wall-square.

The only line of the output should contain three numbers K\ A\ B (separated by a space). If the plan fulfills the king's requirements, all numbers should be zero. Otherwise the three numbers describe a possible path from entrance A to B during which only K (K<F) dragon heads are necessary to be cut off. Entrances are numbered from the top left corner clockwise, beginning with 1. If there are multiple solutions, the minimal K, then the minimal A and B should be computed.

The source code of your program (s34.pas, s34.cpp, ...) and a short documentation (s34.txt, s34.pdf, ...) should be submitted containing a description of your solution and specifying the developer environment to compile your code.

In the example, ``Példa be'' is a sample input, while ``Példa ki'' is the corresponding output.

(10 pont)

Deadline expired on April 15, 2008.


Sorry, the solution is available only in Hungarian. Google translation

Első lépes

Egy programozási/algoritmizálási feladat megoldásának első lépése mindig az absztrakció: azért, hogy a megoldás során valóban a feladatra tudjunk koncentrálni, célszerű a feladat szövegében megjelenő érdektelen részletektől elvonatkoztatni, csak a lényeget kiemelni. Esetünkben a probléma érdemi részét remekül lefordíthatjuk a gráfok nyelvére. A labirintushoz rendeljünk hozzá egy G=\left(V,E\right) súlyozott irányított gráfot a következő módon: a gráf V csúcsai az egyes mezőknek feleljenek meg, élek pedig a szomszédos mezőknek megfelelő csúcsok között fussanak. Az a\inV-ból b\inV csúcsba futó e\inE él c\left(e\right)súlya a-ból b-be jutáshoz levágandó sárkányfejek számát jelölje, azaz a következő legyen: ha b fal, vagy a-ról nem lehet rálépni (kapu miatt), akkor a súly legyen végtelen, egyébként pedig egyezzen meg a b mezőn lévő sárkányfejek számával (ez lehet zérus is). Ezen kívül jelölje d(v,w) a v és w csúcsok közti legrövidebb út hosszát, illetve i(w) egy w bejárati csúcs sorszámát.

Az így kapott gráfban egy A-adik bejárattól B-edikig vezető, K sárkányfej levágását igénylő útvonal a gráfban egy K költségű, a megfelelő csúcsok között futó útnak felel meg. A feladatot pedig a következőképpen fogalmazhatjuk meg: adjuk meg a gráfban a legrövidebb, bejárati csúcsok között vezető x\rightarrowy irányított utat. A megadás az út végpontjainak A=i\left(x\right), B=i\left(y\right) sorszámával, illetve az út K=d\left(x,y\right) hosszával történjen. Több legrövidebb út esetén a legkisebb A, majd B értékűt adjuk meg, ezt a továbbiakban az optimális megoldásnak fogjuk nevezni.

A továbbiakban fontos lesz fejben tartani, hogy az optimális megoldás megadásához lényegében nem mást teszünk, mint az összes bejáratok között futó összes utakat leíró összes \left(K',A',B'\right) számhármasok halmazából kiválasztjuk a legjobbat, azaz a legkisebb K', majd A', majd B' értékűt. A hangsúly azon van, hogy e exponenciális méretű halmaz elemeiből minél kevesebbet kelljen egyáltalán számba vennünk, az optimum kiválasztásához.

Első megközelítés

Kézenfekvő ötlet, hogy minden bejáratból indítunk egy legrövidebbút-keresést az összes többi pontba - például Dijkstra algoritmusával. Ugyanakkor ezzel rengeteg felesleges munkát végzünk: csupán azt szeretnénk tudni ugyanis, hogy F-nél rövidebb út létezik-e egyáltalán egy bejáratból egy másikba, az számunkra teljességgel érdektelen, hogy mindenféle bejáratokból mindenféle pontokba mekkora a legrövidebb utak hossza. Dijkstra algoritmusának futásideje O\left(\left(n+e\right)logn\right), ahol n a gráf csúcsainak, e pedig éleinek a száma, mely utóbbi esetünkben a négyzetháló-topológia miatt n-nel arányos. Mivel az algoritmust minden bejáratra lefuttatjuk, melyből (a oldalhosszú négyzetalakú labirintust feltételezve) O\left(a\right) van, az így kapott algoritmus műveletigénye O\left(a\left(a^{2}+a^{2}\right)loga^{2}\right)=O\left(a^{3}loga\right).

Hasonló módon rengeteg felesleges munkát végeznénk, ha például Warshall algoritmusával meghatároznánk minden pontpárok között a legrövidebb utak hosszát.

Egy hatékony megoldás irányítatlan gráfokra

Az egyszerűség kedvéért oldjuk meg először az előbbi irányítottgráf-modellre felírt problémát egy irányítatlan gráfra, majd ezután terjesszük ki az algoritmust az irányított esetre! Fontos megjegyezni, hogy az irányítatlan gráf már nem modellezi az eredeti feladatot, hiszen például a kapukat sehogyan sem tudjuk reprezentálni. A tárgyalás érdekében azonban mindenképp érdemes bevezetni ezt a további - ha úgy tetszik - veszteséges absztrakciót.

Alkalmazzuk az első bekezdésben bevezett jelöléseket! Bejáratoknak továbbra is a gráf csúcsainak egy adott részhalmazát tekintsük, illetve ahogyan már tárgyaltuk, több megoldás esetén pedig az optimálisnak pedig azt az, melynél az A\neqB értékek a lehető legkisebbek. A két végpont sorrendje most viszont az irányítatlanság miatt érdektelen. Vezessük még be a következőket: jelölje b\left(v\right) a v csúcshoz legközeleb eső bejárati csúcsot (több, azonos távolságra lévő bejárat esetén a legkisebb sorszámút), \dot{d}\left(v\right)=d\left(v,b\left(v\right)\right) pedig v ettől vett távolságát. A w bejárati csúcsokra legyen definíció szerint b\left(w\right)=w.

Tegyük fel, hogy valamilyen módon a b és \dot{d} értékeket már minden csúcsra kiszámoltuk (a d értékeket csak a bizonyításhoz használjuk, a megoldás kiszámításához nem szükségesek). Tegyük fel, hogy az optimális megoldás az A=i\left(x\right) sorszámú x bejárati csúcsból a B=i\left(y\right) sorszámú y-ba érkezik, és K=d\left(x,y\right) költségű!

Lemma 1. Az optimális út minden v csúcsára b\left(v\right)=x vagy b\left(v\right)=y.

Biz. A végpontokra az állítás bejárati csúcs voltuk miatt áll. Egy közbülső v pontra tegyük fel, hogy b\left(v\right)=z\neq x,y. Ez vagy akkor áll fenn, ha d(v,z)<min\left\{ d(v,x),d(v,y)\right\} vagy pedig ha d(v,z)=min\left\{ d(v,x),d(v,y)\right\} de az i\left(z\right) sorszáma kisebb. Ekkor x,y közül bármelyik bejáratot lecserélve z-re az első esetben egy rövidebb, a második esetben pedig egy alacsonyabb bejárati sorszámú, tehát mindkét esetben egy jobb utat kapnánk, ami ellentmond annak a feltételnek, hogy az eredeti út optimális.

Lemma 2. Az optimális útnak van olyan \left\{ v,w\right\} éle, hogy b(v)=x és b(w)=y. Ezekre az élekre c\left(v,w\right)+d(v,x)+d(w,y)=d\left(x,y\right).

Biz. Mivel az út csúcsainak b-értéke az 1. lemma miatt csak x vagy y lehet, és a végpontok b-értékei különböznek, biztosan van egy ilyen él. A második állítás pedig azért igaz, mivel a bal oldalon is az x-y út hossza szerepel, csak három szakaszra (x-v,v-w,w-y) egyenként összegezve.

A 2. lemma állítását felhasználva azonnal konstruálhatunk is egy algoritmust a feladat megoldására. Vegyük ugyanis sorra a gráf éleit, és minden \left\{ v,w\right\} élre képezzük az adott élen áthaladó utat leíró \left(K',A',B'\right) számhármast a következő módon:

A'=i\left(b\left(v\right)\right)

B'=i\left(b\left(w\right)\right)

K'=c\left(v,w\right)+\dot{d}(v)+\dot{d}(w)

Az így képzett legális (A'\neqB') számhármasokat mint potenciális megoldásokat jegyezzük meg, majd közülük válasszuk ki a legjobbat, azaz a legkiseb K', majd A', majd B' értékűt. Az így kapott számhármas épp az optimális megoldást írja, hiszen a 2. lemma miatt a gráf tartalmazott legalább 1 olyan \left\{ v,w\right\} élet, melyre:

b(v)=x, így A'=i\left(b\left(v\right)\right)=i\left(x\right)

b(w)=y, így B'=i\left(b\left(w\right)\right)=i\left(y\right)

c\left(v,w\right)+d(v,x)+d(w,y)=d\left(x,y\right), így K'=c\left(v,w\right)+\dot{d}(v)+\dot{d}(w)=c\left(v,w\right)+d(v,x)+d(w,y)=d\left(x,y\right)

Azaz az ebből az élből képzett \left(K',A',B'\right) hármas épp az optimális megoldást leíró \left(K=d\left(x,y\right),A=i\left(x\right),B=i\left(y\right)\right) hármassal egyezik meg, azaz a potenciális megoldások között az optimális megoldás is szerepelt, így amikor közülük a legjobbat kiválasztottuk, az épp az optimális megoldás volt.

Már csak a b-értékek, illetve az egyes pontok legközelebbi bejárattól vett \dot{d}\left(v\right)=d\left(v,b\left(v\right)\right) távolságértékeinek a meghatározása maradt hátra. A bejárati csúcsokra \dot{d}\left(w\right)=0 és b\left(w\right)=w . Ezután pedig Dijkstra algoritmusának egyszeri lefuttatásával megkaphatjuk a két értéket az összes többi pontra (a legrövidebbút-keresést az összes bejárati csúcsból egyszerre indítva, a b-értékeket a minimumot adó őstől másolva).

A megoldás kiterjesztése irányított gráfokra

Irányított élek esetén mindössze annyi változik, hogy mind a \dot{d}, mind pedig a b értékekből két készletünk van: az egyik arra vonatkozik, amikor az élek irányításának megfelelően haladunk (b_{e},\dot{d}_{e}), a másik pedig az irányítással ellentétes haladásra (b_{v},\dot{d}_{v}). Kiszámításuk külön-külön, az előző bekezdésben leírt módon történik, tehát összesen 2 db legrövidebút-keresésre van szükségünk. Az éleket sorban megnézve a \left(v,w\right) irányított él a következő potenciális megoldást adja:

A'=i\left(b_{v}\left(v\right)\right)

B'=i\left(b_{e}\left(w\right)\right)

K'=c\left(v,w\right)+\dot{d}_{v}(v)+\dot{d}_{e}(w)=c\left(v,w\right)+d_{v}(v,x)+d_{e}(w,y)

Az optimális megoldást itt is a potenciális megoldásokat leíró számhármasok közül a legjobbat választva kapjuk.

A algoritmus műveletigénye általános esetben O\left(e+\left(n+e\right)logn\right), mivel konstans számú (2 db) legrövidebbút-keresést hajtunk végre, illetve egyszer végiglépkedünk az összes élen. Esetünkben a gráf kötött felépítése miatt a műveletigény O\left(a^{2}+\left(a^{2}+a^{2}\right)loga^{2}\right)=O\left(a^{2}loga\right), ami felhasználva, hogy az élsúlyok egy kis elemszámú halmazból származnak (0...9, ha végtelen súly esetén az élet kitöröljük) Dijkstra algoritmusának mozgókupacos megvalósításával O\left(a^{2}\right)-re csökkenthető, azaz a feladat meglepő módon a mezők számával egyenesen arányos időben megoldható.

Engedy Balázs


Statistics:

5 students sent a solution.
7 points:2 students.
5 points:1 student.
4 points:1 student.
2 points:1 student.

Problems in Information Technology of KöMaL, March 2008