Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FR_10_12 - Haft

Małgosia na prostokątnej tkaninie o rozmiarach m × n cm wyszyła pewną liczbę gwiazdek o rozmiarach 1 × 1 cm. Kiedy jej kolega Jaś zobaczył ten przepiękny haft, zapragnął mieć taki sam.

Nasz bohater posiada maszynę do haftowania. Urządzenie to reprezentuje tkaninę jako tabelę o m wierszach i n kolumnach. Wiersze numerowane są od góry do dołu, od 1 do m. Kolumny numerowane są od lewej do prawej, od 1 do n. Komórka tabeli odpowiada fragmentowi tkaniny o rozmiarze 1 × 1 cm. Maszyna może wykonać maksymalnie m × n operacji haftowania. W ramach pojedynczej operacji urządzenie wyszywa gwiazdkę w kolumnie x wiersza y, a następnie po r gwiazdek:

  • pionowo w górę
  • pionowo w dół
  • poziomo w lewo
  • poziomo w prawo

Wartość r musi być dodatnią liczbą całkowitą. W przypadku, gdy w jakiejś komórce był już wykonany haft, maszyna ją pomija. Operacja powodująca próbę wyszycia gwiazdki poza obszarem tkaniny kończy się uszkodzeniem urządzenia.

Przykładowy haft dla r = 1

.*.
***
.*.

Przykładowy haft dla r = 3

...*...
...*...
...*...
*******
...*...
...*...
...*...

Jaś posiada taką samą tkaninę jak Małgosia. Odpowiedz na pytanie. Czy nasz bohater jest w stanie, za pomocą posiadanej maszyny, odwzorować haft swojej koleżanki?

Wejście

W pierwszej linii wejścia znajdują się dwie liczby całkowite m ∈ [3, 1000] i n ∈ [3, 1000] określające rozmiar tkaniny Małgosi.

W kolejnych m wierszach znajduje się po n znaków opisujących zawartość kolejnych cm2 tkaniny. Znak * oznacza, że na danym cm2 Małgosia wyszyła gwiazdkę. Znak . oznacza, że dany cm2 nie był zmieniany.

Wyjście

Jeżeli Jaś nie jest w stanie, za pomocą posiadanej maszyny, odwzorować haftu Małgosi na wyjściu należy wypisać -1.

W przeciwnym wypadku w pierwszej linii wyjścia należy wypisać liczbę operacji haftowania do wykonania, zaś w kolejnych ich opis. Każda operacja powinna zostać scharakteryzowana za pomocą 3 liczb całkowitych x, y i r oznaczających odpowiednio współrzędne komórki, w której rozpoczyna się wyszywanie oraz długość promieni.

Jeżeli istnieje wiele rozwiązań, wypisz dowolne z nich.

Przykład 1

Wejście:

7 5
.....
.*.*.
*****
.*.*.
*****
.*.*.
.....

Wyjście:

4
2 3 1
4 3 1
2 5 1
4 5 1

Przykład 2

Wejście:

4 6
......
.****.
.****.
......

Wyjście:

-1

Dodane przez:Maciej Boniecki
Data dodania:2018-12-20
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.