Runda 5 - Łódź podwodna

19.10.2009 - Rafał Nowak
TrudnośćTrudnośćTrudność

 Zawody stałe, runda 5

Limit czasowy: 18s ; Limit pamięciowy: 32 MB

 


Łódź podwodna

 

Profesor Lake właśnie ukończył projekt najnowszego modelu drewnianej łodzi powodnej, z którego jest bardzo dumny; zob. rysunek poniżej. Ma nadzieję, że za pomocą swej łodzi będzie można badać nowe obszary mórz i oceanów, przez co dojdzie do wielu nowych odkryć.

Profesor dysponuje mapami wybranych obszarów mórz i oceanów. Każda mapa zawiera, między innymi, informacje o głębokości terenu podaną w prostokątnej tablicy liczb całkowitych nieujemnych.

Celem profesora jest zbadanie jak największego obszaru każdej mapy. Chce on więc rozpocząć podróżowanie po dnie oceanu z pewnego konkretnego pola na mapie. Niestety konstrukcja łodzi pozwala jedynie na przemieszczanie się pomiędzy sąsiednimi polami tylko w pozycjach poziomych i pionowych (z punktu widzenia mapy). Oczywiście nie to jest wielkim ograniczeniem nowej łodzi podwodnej profesora Lake'a. Jest jednak jeszcze jeden problem. Z powodu materiałów kontsrukcyjnych łódź podwodna jest ograniczona co do wahań ciśnienia pod wodą, a w konsekwencji możną nią podróżować jedynie po takich polach, których najmniejsza i największa głębokość różnią się co najwyżej o P, gdzie 0 P 20. Wartość P może być różna dla różnych map.

 

Zadanie:

Napisz program, który pomoże profesorowi obliczyć rozmiar największego obszaru (dla każdej z map), jaki można zwiedzić podróżując łodzią podwodną. Rozmiarem obszaru jest liczba pól, jakie da się zwiedzić podczas podróży.

 

Wejście:

W pierwszej linii wejścia znajduje się liczba map (zestawów danych), jakimi dysponuje profesor Lake. Możesz założyć jest ona dodatnią liczbą całkowitą, nie większą od 20. Następnie podane są opisy map (zestawów danych) oraz parametr P łodzi podwodnej. W pierwszym wierszu każdego opisu podany jest parametr P opisujący maksymalną różnicę głębokości pól, jakie może zwiedzić łódź podwodna. W drugim wierszu podany jest rozmiar mapy w postaci dwóch liczb A i B (1 ≤ A,B ≤ 300), oznaczających kolejno liczbę wierszy i kolumn tablicy z głębokościami pól na mapie. Następnie podanych jest A wierszy, a w każdym B liczb oznaczających głębokości pól na mapie. Każda głębokość jest liczbą całkowitą z zakresu [0, 109].

 

Wyjście:

Dla każdej mapy należy wypisać rozmiar największego obszaru, jaki można zwiedzić za pomocą łodzi podwonej profesora.

 

Przykłady

Wejście:

1

3

4 6

10 13 16 11 12 19

11 11 29 12 14 19

42 42 39 12 22 33

13 13 49 15 15 39

 

Wyjście:

6

 

Największy możliwy obszar do zwiedzenia na pierwszej mapie to (nieskreślone pola)

 

10 13 16 11 12 19

11 11 29 12 14 19

42 42 39 12 22 33

13 13 49 15 15 39

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzas
1Anna Piekarska10137:15:00
2Kuba Skudlarski10150:10:01
3Maciej Szeptuch10183:09:40
4Michal Zgliczynski102215:25:26
5Mateusz Wasilewski103560:36:19
6Maciej Kisiel105937:33:10
7Igor Adamski107427:46:22
8Michał Karpiński108070:50:35
9Darek Bukowski1154:21:29
10Agnieszka Dudek1155:22:04
5
Twoja ocena: Brak Ocena: 5 (2 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com