Hide

Problem E
Fältet

\includegraphics[width=8cm]{Field.jpg}

Bönderna Östen Östlund och Väsbjörn Westlund bor på var sin sida om ett rektangulärt fält. Östen vill släppa ut sina får på fältet för att beta, men eftersom fältet är genomkorsat av staket är Östen osäker på hur stor del av fältet som tillhör honom, hur stor del som tillhör Väsbjörn, och hur stor del som är allmänning (där båda kan släppa ut sina får). Väsbjörn vill veta samma sak, och de behöver nu din hjälp för att räkna ut svaret.

Uppgiften består i att utifrån en karta av fältet räkna ut antal rutor som tillhör Östen, antal rutor som tillhör Väsbjörn, och antal rutor som är allmänning. Östen äger alla rutor som kan nås från den vänstra kanten av fältet, medan Väsbjörn äger alla rutor som kan nås från den högra kanten. De rutor som kan nås från både vänstra och högra kanten räknas som allmänning. De rutor som innehåller staket, eller som inte kan nås vare sig från den vänstra eller högra kanten, ska inte räknas alls. En ruta $R$ kan nås från en annan ruta $S$ om de har en gemensam kant, alltså om $R$ är ovanför, nedanför, till vänster eller till höger om $S$. Om $R$ och $S$ bara sitter ihop i ett hörn (diagonalt), så kan man inte$S$ från $R$ eller vice versa.

Indata

Indata inleds med två heltal $a$ och $b$ som anger antal rader och kolumner på fältet. Därefter följer $a$ rader som var och en innehåller $b$ tecken. Ett tecken är antingen ett ’x’, som markerar en bit av ett staket, eller en punkt ’.’, som markerar en bit mark. Du kan förutsätta att $a\leq 100$ och $b\leq 100$.

Utdata

Utdata ska bestå av tre heltal, separerade med mellanslag. Det första talet ska markera hur många rutor som kan nås från vänstra kanten av fältet, det andra talet hur många rutor som kan nås från högra kanten, och det tredje talet hur många rutor som kan nås från både vänstra och högra kanten.

Sample Input 1 Sample Output 1
2 5
.x.x.
..x..
3 3 0
Sample Input 2 Sample Output 2
7 10
.xxxx...x.
x......x..
..xxxx.xxx
xx.....x..
x......x.x
x.xxxxxx.x
x........x
1 3 36

Please log in to submit a solution to this problem

Log in