Informatika gyűjtemény

Egy szinttel feljebb Üldözés

2004050607080910

NézetNyomtat

Üldözés

Egy (végtelen) $101 \times 101$-es négyzethálón üldöz egy rendőrautó egy bűnözőkkel megpakolt autót. A bünözők kocsija a négy élszomszédos mezőre léphet, a rendőr két egységet lép előre vagy jobbra, de nem kanyarodhat balra.
Kezdetben a rendőrautó a (0,0) mezőn áll és "felfelé néz". Vizsgáljuk program segítségével, hogy melyek azok a kiinduló mezők, amelyekről indulva a bűnözők elmenekülhetnek.
A rendőrautó akkor kapja el a bűnözőket, ha pont arra a mezőre lép, amelyen állnak, vagy a 4 élszomszédos, illetve a négy csúcsszomszédos mező valamelyikére tud lépni. (Tehát mindig egy $3\times 3$-as területet "üt".)
A megmenekülést kétféle módon is definiálhatjuk:
  • kiér a pályán kívülre
  • tetszőlegesen sokáig elkerülheti, hogy elkapják