Feladatok‎ > ‎

Fa nélküli terület

Egy gazdag üzletember egy óriási villát szeretne építeni családjának és magának. Helyszínként egy csendes-óceáni kis téglalap alakú szigetecskére esett a választása. A szigetnek gyönyörű és egyedülálló növényvilága van, ezért úgy szeretné megépíteni a házát, hogy közben egyetlen fának sem esik bántódása.

A szigetet felosztotta N×M négyzetegységre, és mindegyik négyzetegységről megállapította, hogy van-e rajta fa. Ha van, akkor a térképén a megfelelő négyzetbe egy 'X'-et rajzolt, ellenkező esetben egy '.'-ot. Segíts neki megtalálni a legnagyobb területű rácsvonalakra illeszkedő téglalapot, ami egyáltalán nem tartalmaz fákat!

A bemeneted első sorában kapsz két számot, N-et és M-et (1<=N,M<=30), majd N sorban M karaktert 'X'-ekből és '.'-okból. Add meg a legnagyobb területű üres téglalap bal felső és jobb alsó pontjainak koordinátáit! Ha több ilyen van, elég egyet megadnod!

Példa bemenetek

12 23
X...X......XXX.XX.X....
....X..X..X..X.X.......
.X.....X...X....X..X..X
X.....X...X......X..X..
..X..X....X...XX.....X.
X...X..XX......X..X...X
..X.XXXX.X....X..X..X..
.X.X.....XX...X....X.X.
..X.XXX..X.X...X...X.XX
.....X...X........X....
...X....X......X..X....
..X.....X.....X.....X..

30 30
..X..X...X....X.X...X.X...X..
X....XX.X...X..X.X......X....
...X..XX..X..X......XXXX..X.X
....X.X..XX.....X.XX.....X...
....X....X...X..X..XX...X....
...X.X....XX.X.XX..XX......X.
XXX......XXX...X...........X.
XX.X..XX.X....X.....X.XX....X
.X.X......X........X....X.XX.
.XX..XXX..XX..X.....XX.....XX
XX.XX.X..XX.X.X...X........X.
X..X.....XX......X..X..X...XX
..XX..X.....XX.....X.X..X.X.X
X.X.X......X.....X......X.X..
X..X...X..X.X........X..X..XX
.X...XX..X.....X....XX..X....
X..XX....X.....X....XX..X...X
X.X..X.......XXX.....XX.....X
...X.X..X.....X....X.......X.
....XX.X..........X.X.X......
.XX.X...X.X.X........X.X.X...
X...X..X..X...X....XX.X...X..
.X...X......XXX.X..........X.
XX.....X...........X.........
..X..X...X.X....X.XX.X.X.....
X...X.........XX....XX.X...X.
...X.XX.X....X.XX...XX....X..
.XXX....XX...X.X.XX.X....X.X.
.X......X.......XX.....X..X.X