Distància màxima P99716


Statement
 

pdf   zip

html

Considereu un món bidimensional. La distància Manhattan entre dues posicions (i1, j1) i (i2, j2) es defineix com | i1i2 | + | j1j2 |. Per exemple, la distància entre (7, 3) i (2, 9) és | 7 − 2 | + | 3 − 9 | = 5 + 6 = 11.

Donada una matriu M amb n files i m columnes, trobeu la màxima distància Manhattan entre tots els parells de posicions (a, b) i (c, d) tals que M[a][b]M[c][d].

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n i m, seguides de la matriu en n línies, cadascuna amb m enters. La matriu té entre 2 i 105 valors entre 1 i 109.

Sortida

Per a cada matriu, escriviu la màxima distància Manhattan entre tots els parells de posicions amb valors diferents. Cada matriu tindrà almenys dos valors diferents.

Public test cases
  • Input

    1 2
    1000 2000
    
    3 1
    1000000000
    999999999
    999999998
    
    2 5
    42 42 42 42 42
    42 42 10 23 42
    

    Output

    1
    2
    4
    
  • Information
    Author
    Izan Beltrán
    Language
    Catalan
    Official solutions
    C++ Python
    User solutions
    C++