Hlídání na zkoušce

Kam si má sednout učitel, aby při zkoušce viděl na co nejvíc studentů?

V den písemné zkoušky přijdou studenti do učebny a libovolně se rozsadí do lavic. Na které z volných míst si má sednout učitel, pokud chce mít výhled na co největší počet přítomných studentů? Jeden student zakrývá druhého jen tehdy, pokud student sedící dále od učitele leží na přímce vedoucí od učitele k bližšímu studentovi.

Rozsazení studentů ve třídě je reprezentováno jako dvoudimenzionální pole (seznam seznamů) o rozměrech (m x n) obsahující nuly a jedničky. Nula znamená, že místo je volné, a jednička, že je obsazené studentem. Třída obsahuje určitý počet řad (n) a určitý počet míst v jedné řadě (m).

V modulu solver.py vytvořte funkci find_seat(), která na základě rozesazení studentů ve třídě vrátí souřadnice místa, kam si má sednout učitel, aby viděl na co nejvíce studentů. Soubor solver.py pak odešlete do odevzdávacího systému.

• Předpokládáme, že učitel se na vybraném místě může otáčet a vidí tedy do všech směrů.
• V případě, že by přicházelo v úvahu více optimálních míst, vraťte libovolné z nich.
• Učitele lze posadit jen na místo, kde nesedí student (tj. na místo, které ve 2D poli obsahuje 0).
• V programu číslujte od 0, tj. 1. souřadnice je v rozmezí 0 až len(seats) - 1 (počet řad mínus 1) a 2. souřadnice je v rozmezí 0 až len(seats[0]) - 1 (počet míst v řadě mínus 1).
• Zanedbejte rozměry studenta, každý student je ideální bod.

Pokud se studenti posadí na místa označená *,

    0 1 2 3
    -------
0 | * . * *
1 | . * * .
2 | * . * .
3 | * * . *
4 | * * * *

pak tomuto rozesazení odpovídá 2D pole [[1,0,1,1],[0,1,1,0],[1,0,1,0],[1,1,0,1],[1,1,1,1]]. Bude-li funkce find_seat() správně implementovaná, její volání pro tento vstup by mělo vypadat asi takto:

>>> find_seat([[1,0,1,1],[0,1,1,0],[1,0,1,0],[1,1,0,1],[1,1,1,1]])
[2,1]

Z místa na řádku 2 ve sloupci 1 uvidí učitel 12 studentů. Stejný počet by viděl i z místa [2, 3], což by byl také správný výsledek funkce.

Pro jinak velkou třídu, kde se studenti rozsadí takto:

    0 1 2 3 4
    ---------
0 | * . * * *
1 | . * . . *
2 | * * . * .
3 | . * * * *
4 | * . * * .

by volání funkce mělo vypadat následovně:

>>> find_seat([[1,0,1,1,1],[0,1,0,0,1],[1,1,0,1,0],[0,1,1,1,1],[1,0,1,1,0]])
[1,2]

Z místa [1,2] učitel uvidí na 14 studentů, a takové místo je ve třídě jediné.

1. Za úlohu můžete získat až 10 bodů, úměrně k tomu, kolik rozesazení se vám podaří správně vyřešit.
2. Vaše řešení bude otestováno na 5 jednodušších (rozměry třídy max. 5×5) a 15 složitějších (rozměry třídy max. 30×30) rozesazeních.
3. Pokud dojde při jakémkoli testu k chybě (funkce nevrací seznam, nevrací dvě souřadnice, obsahuje nekonečnou smyčku,…), získáte 0 bodů.
4. Hodnoceno je i částečně správné řešení, kdy funkce vrátí prázdné místo, kde nesedí student, avšak toto místo není optimální.