Здравствуйте, Vintik_69, Вы писали:

V_>Здравствуйте, mehas, Вы писали:

M>>Здравствуйте, Трурль, Вы писали:

Т>>>Нет ли еще какого способа?

M>>Можно найти диаметр и за линейное время от размера поля. Будем сжимать поле с краев, т.е:

M>>1) добавим в очередь все вершины, соответствующие областям, которые касаются краев поля
M>>2) делаем BFS, отталкиваясь от вершин в очереди
M>>3) количество итераций bfsа = диаметру, последняя выброшенная из очереди вершина — центр

V_>Это неверно. Например, на таком тесте алгоритм даст 1, а должно быть 2:
V_>

010
V_>101
V_>010

Мда, точно.
ну, по крайней мере можно сократить до O(N^3), если пустить BFSы только от крайних областей и выбрать максимум.