Bitmapa

Limit pamięci: 32 MB

Dana jest prostokątna bitmapa o rozmiarach . Każdy piksel bitmapy jest albo biały, albo czarny, przy czym co najmniej jeden jest biały. Piksel w -tym wierszu i -tej kolumnie bitmapy nazywamy pikselem . Odległość dwóch pikseli oraz określamy jako:

.

Zadanie

Napisz program, który:

  • wczytuje ze standardowego wejścia opis bitmapy,
  • dla każdego piksela oblicza odległość do najbliższego piksela białego,
  • wypisuje wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się para liczb całkowitych , oddzielonych pojedynczym odstępem, , . W każdym z kolejnych wierszy wejścia zapisano dokładnie jedno słowo zero-jedynkowe o długości - opis jednego wiersza bitmapy. Na pozycji w wierszu , , , znajduje się 1 wtedy i tylko wtedy, gdy piksel jest biały.

Wyjście

W -tym wierszu standardowego wyjścia, , należy wypisać liczb całkowitych pooddzielanych pojedynczymi odstępami i takich, że jest odległością piksela od najbliższego piksela białego.

Przykład

Dla danych wejściowych:

3 4
0001
0011
0110

poprawną odpowiedzią jest:

3 2 1 0
2 1 0 0
1 0 0 1

Autor zadania: Marcin Sawicki.