Problem F
Stigspel

Två spelare spelar ett stigspel på ett rutat bräde. De får fylla i ett o eller ett x varannan gång. Den som lyckas förbinda sina två sidor med en sammanhängande stig vinner. Givet en avslutad spelplan, avgör om spelare x, spelare o, eller ingendera har vunnit. Om spelet inte har följt reglerna skall "fusk" anges.

Spelare anses ha fuskat om antalet x eller o tyder på att spelarna inte har gjort vartannat drag. Om någon spelare förbinder två sidor (x ska förbinda topp med botten, o höger med vänster) med en sammanhängande serie av sitt tecken har denne vunnit. Tecken anses tillhöra samma sammanhängande serie om de ligger rakt över, under eller bredvid varandra, och är samma bokstav. Diagonaler räknas alltså inte. Det är möjligt att spelets gång leder till förgreningar, loopar, multipla förbindelser, etc. Den spelare som har minst en serie tecken som sammanbinder sina två motstående kanter har vunnit.

Indata

Första raden i indata är två heltal, 1 – 10000 (inklusivt), där det första talet M anger antalet rader, och det andra talet N anger antalet kolumner på spelplanen. Därefter följer M rader med N tecken i varje rad, som representerar spelplanen. Tecknen är antingen ’x’ eller ’o’.

Utdata

Om det inte är fusk och någon spelare har vunnit ska programmet skriva ut ett ensamt ’x’ eller ’o’ för att ange vem som vann, eller ordet ’ingen’ om ingen spelare har vunnit. Om den angivna spelplanen inte kan ha uppkommit utan fusk ska programmet skriva ut ordet ’fusk’.

6 6
xooxoo
xxoxxo
xoxoxo
oxoxxo
ooxxoo
xxxoxo

x

1 1
o

o