algorytm labirynt pokrycie

Witam,
mam problem z zadaniem które polega na znalezieniu minimalnego pokrycia ścieżkowego tak aby ścieżki się nie przecinały (ścieżkami prostymi) labiryntu, który jest reprezentowany przez macierz NxM pól które mogą być zajęte albo wolne, dodatkowym założeniem jest to że obszar wolny(ten który należy pokryć ścieżkami) jest spójny.
Przykładowo minimalne pokrycie dla labiryntu 4x4 wyglądającego tak

++++++
+   #+
+# # +
+    +
+ # #+
++++++

może być takie:

++++++
+111#+
+#3#2+
+3322+
+3#2#+
++++++

Ktoś ma jakiś pomysł?? Bo jak dla mnie w ogólnym przypadku jest to problem NP-zupełny i nie ma innego sposobu jak tylko zbadać wszystkie możliwości...

obszar wolny ma być spójny, a czy dozwolone są cykle obszaru wolnego?
Najprostszy przykład:

++++++
+    +
+ # #+
+    +
++++++

tak są dozwolone cykle jak i komnaty, czyli na przykład

++++++
+   #+
+   #+
+ #  +
++++++

wiem że jakby nie było cykli to problem byłby pewnie do rozwiązania algorytmem bellmana-forda z ujemnymi wagami, żeby wyszukiwać kolejno maksymalne ścieżki...

coś to nie konsystentne najpierw piszesz:

jakkrzysiek napisał(a)

dodatkowym założeniem jest to że obszar wolny(ten który należy pokryć ścieżkami jest spójny.
a potem:

jakkrzysiek napisał(a)

tak są dozwolone cykle jak i komnaty

Zacząłbym od obchodzenia labiryntu zasadą prawej ręki. Po każdym kroku ujmowałbym kolejne wolne pola. Jak zajdę w kozi róg to wtedy zacząć nową ścieżkę. Jak na razie nie potrafię wymyśleć sytuacji, w której takie podejście by zawiodło.

Po zastanowieniu jest jednak taka możliwość (duża komnata):

#########
#       #
#      ##
#      ##
#      ##
###### ##
#      ##
#########

rozwiązaniem jest jedna ścieżka

spójny czyli taki gdzie z dowolnego wolnego miejsca można dojść w dowolne inne wolne miejsce, a komnaty miałem na myśli obszary wolne które nie są wąską ścieżką ;)... też myślałem nad tym myślałem... ale jakoś nic sensownego mi nieprzychodzi do głowy,
dzięki za zainteresowanie ;)