VI Olimpiada Informatyczna 1998/99
|
Zadanie: BIT
|
Autor: Marcin Sawicki
|
Etap II, dzień drugi | 11 lutego 1999 |
Plik źródłowy: | BIT.??? (np. pas, c, cpp) |
Plik wykonywalny: | BIT.exe |
Plik wejściowy: | BIT.in |
Plik wyjściowy: | BIT.out |
Dana jest prostokątna bitmapa o rozmiarach n*m. Każdy piksel bitmapy jest albo biały, albo czarny, przy czym co najmniej jeden jest biały. Piksel w i-tym wierszu i j-tej kolumnie bitmapy nazywamy pikselem (i,j). Odległość dwóch pikseli p1=(i1,j1) oraz p2=(i2,j2) określamy jako:
Napisz program, który:
W pierwszym wierszu pliku tekstowego bit.in znajduje się para liczb całkowitych n,m oddzielonych pojedynczym odstępem, 1<=n <=182, 1<=m<=182. W każdym z kolejnych n wierszy pliku bit.in zapisano dokładnie jedno słowo zero-jedynkowe o długości m - opis jednego wiersza bitmapy. Na pozycji j w wierszu (i+1), 1 <= i <= n, 1 <= j <= m, znajduje się '1' wtedy i tylko wtedy, gdy piksel (i,j) jest biały.
W i-tym wierszu pliku wyjściowego bit.out, 1<=i<=n, należy wypisać m liczb całkowitych f(i,1),...,f(i,m) pooddzielanych pojedynczymi odstępami i takich, że f(i,j) jest odległością piksela (i,j) od najbliższego piksela białego.
Dla pliku wejściowego bit.in:
3 4 0001 0011 0110
poprawną odpowiedzią jest plik tekstowy bit.out:
3 2 1 0 2 1 0 0 1 0 0 1
Na stronie: http://www.mimuw.edu.pl/~msawicki/stereo.html dostępny jest applet Stereogram, który był pierwowzorem tego zadania.