Üzletek

Egy vállalkozásnak egy raktára (piros belsejű kör a bal alsó sarokban) és több üzlete (zöld belsejű kör) is van. A raktárból elindulva árut szeretnének szállítani az összes üzletbe a rácshálóval jelzett utcákon. A szállításhoz az alábbi lépéseket tehetik (az egyes lépések az adott irányba :db utcát tesznek meg):

• fel(db)
• le(db)
• balra(db)
• jobbra(db)

Add meg, hogy a vállalkozás az összes üzletbe milyen legrövidebb lépéssorozattal tudja kiszállítani az árukat! (Az utolsó üzlet után nem kell sehova visszamennie.)

Például a raktártól a baloldali első üzlethez 7 lépéssel a fel(5) jobbra(2) utasítássorral juthat el (de a fel(1) jobbra(1) fel(1) jobbra(1) fel(3) is jó).

1. B.

C:

A minimális lépésszámú megoldások 15 pontot érnek, az ennél nagyobb lépésszámúak annyival kevesebbet, ahány lépéssel hosszabbak.

A. A minimális lépésszám 18. Egy lehetséges megoldás: fel 5 jobbra 2 fel 2 jobbra 1 jobbra 1 le 3 le 1 jobbra 3

B. A minimális lépésszám 16. Egy lehetséges megoldás: fel 4 jobbra 4 balra 2 fel 1 jobbra 1 fel 2 jobbra 2

C. A minimális lépésszám 16. Egy lehetséges megoldás: fel 5 jobbra 2 le 1 jobbra 2 jobbra 1 fel 3 balra 2