Psst... Ruszyły zawody olimpiady informatycznej dla uczniów szkół podstawowych i średnich. Zadania na tych konkursach są bardzo podobne do zadań, które rozwiązujesz, tutaj, na Szkopule.
Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/

Zadanie Gra w podwajanie (gra)

Gra w podwajanie

Limit pamięci: 128 MB

Gra w podwajanie to właściwie bardziej łamigłówka niż gra. Plansza do gry ma kształt prostokąta podzielonego na pola będące kwadratami jednostkowymi. Na początku niektóre pole zawierają żeton, a niektóre nie.

Celem gracza jest zgromadzenie jak największej liczby żetonów na jednym polu. Jedyny dostępny ruch polega na znalezieniu dwóch pól stykających się bokiem zawierających taką samą (dodatnią) liczbę żetonów i przełożeniu wszystkich żetonów z jednego z tych pól na drugie.

Napisz program, który mając daną początkową konfigurację planszy, dla każdego pola wyznaczy maksymalną liczbę żetonów, jakie gracz mógłby zgromadzić na tym polu.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite oraz () oznaczające liczbę wierszy oraz liczbę kolumn planszy. Każdy z kolejnych wierszy zawiera ciąg cyfr 0 lub 1. Cyfra 1 oznacza pole zawierające żeton, a cyfra 0 - pole wolne.

Wyjście

Twój program powinien wypisać wierszy zawierających po liczb całkowitych. -ta liczba w -tym wierszu powinna oznaczać maksymalną liczbę żetonów, jakie gracz mógłby zgromadzić na polu położonym na przecięciu -tego wiersza i -tej kolumny, zaczynając z podanej konfiguracji początkowej.

Przykład

Dla danych wejściowych:

poprawną odpowiedzią jest:

0 2 4 4
2 0 4 4
2 0 4 4

Powyższy przykład wyjaśnia, w jaki sposób na polu na przecięciu środkowego wiersza i ostatniej kolumny można zgromadzić 4 żetony.

Autor zadania: Jakub Radoszewski.