eolymp
bolt
Try our new interface for solving problems
Məsələlər

Пятна на бумаге

Пятна на бумаге

На лист клетчатой бумаги размерами \textbf{M}×\textbf{N} случайно капнули чернилами, так что образовалось несколько пятен. Каждая клетка листа считается либо закрашенной, либо чистой. Две закрашенных клетки принадлежат одному пятну, если существует путь от одной клетки до другой, проходящий по закрашенным клеткам этого пятна, причём переходить в соседнюю клетку можно только по горизонтали или вертикали. Определите количество получившихся пятен и площадь самого большого пятна, т.е. количество клеток, занятых этим пятном. \InputFile В первой строке входного файла заданы величины \textbf{M} и \textbf{N} (\textbf{1} ≤ \textbf{M}, \textbf{N} ≤ \textbf{10^5}, \textbf{1} < \textbf{M·N} ≤ \textbf{10^6}). Каждая из последующих \textbf{M} строк содержит \textbf{N} символов \textbf{0} или \textbf{1}, где ноль соответствует чистой, а единица --- закрашенной клетке. Гарантируется, что хотя бы одна клетка будет закрашена. \OutputFile Выведите два числа: количество получившихся пятен и площадь самого большого пятна.
Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri #1
6 7
1001001
1111011
1001000
1001111
0100000
0000000
Çıxış verilənləri #1
3 13
Mənbə NEERC Western Subregional Contest 2012