Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Az S. 150. feladat (2021. február)

S. 150. Van egy \(\displaystyle N\times M\) mezőből álló játéktáblánk, melynek egyes mezői lyukasak. Van továbbá egy \(\displaystyle 1\times 1\times 2\) oldalú téglatestünk, melyet a következő szabályok szerint mozgathatunk a táblán: a téglatestnek minden lépés után teljes felületével szilárd mezőn kell állnia (különben leesik); a téglatestet minden lépésben egy hosszú vagy egy rövid, a talajon lévő élén átforgatva mozgathatjuk a szomszédos mezőkre.

Arra vagyunk kíváncsiak, hogy el lehet-e juttatni a táblán elhelyezett téglatestet a kiinduló mezőjéről egy adott célmezőre. A téglatestnek a kiinduló és a célmezőjén is egy \(\displaystyle 1\times 1\)-es oldalán kell állnia.

Bemenet: az első sor tartalmazza a tábla sorainak és oszlopainak számát, azaz \(\displaystyle N\)-et és \(\displaystyle M\)-et. A következő \(\displaystyle N\) sor mindegyikében \(\displaystyle M\) karakter található. Az \(\displaystyle i\)-edik sor \(\displaystyle j\)-edik karaktere ,,#'', ha a mező nem lyukas, és ,,.'', ha a mező lyukas. A következő sorban a megválaszolandó kérdések \(\displaystyle Q\) száma szerepel. Az utána lévő \(\displaystyle Q\) sor mindegyikében egy téglatest kezdő mezőjének sor- és oszlopindexe, majd egy célmező sor- és oszlopindexe szerepel szóközzel elválasztva. A sorokat és oszlopokat nullától indexeljük.

Kimenet: az a szám, ahány kérdésre igen a válasz.

Példa:

Magyarázat: az első téglatest az alábbi lépésekkel eljuthat a célba: elfektetés a \(\displaystyle (3,1)\) és \(\displaystyle (3,2)\) mezőkre, felállítás a \(\displaystyle (3,3)\)-ra, elfektetés az \(\displaystyle (1,3)\) és \(\displaystyle (2,3)\) mezőkre, átfordítás az \(\displaystyle (1,4)\)–\(\displaystyle (2,4)\)-re, felállítás a \(\displaystyle (0,4)\)-re. A második téglatest nem juttatható el a célba álló helyzetben.

Korlátok: \(\displaystyle 1\le N, M\le 200\), \(\displaystyle 1\le Q\le 10\,000\). Időkorlát: 0,5 mp.

Értékelés: A pontok 50%-a kapható, ha \(\displaystyle Q=1\).

Beküldendő egy s150.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható.

(10 pont)

A beküldési határidő 2021. március 16-án LEJÁRT.


Statisztika:

Az S. 150. feladat értékelése még nem fejeződött be.


A KöMaL 2021. februári informatika feladatai