Caselles segures P50250


Statement
 

pdf   zip

thehtml

Considereu un tauler d’escacs n × m, on només hi ha t torres. Quantes caselles segures té? En aquest problema, diem que una casella és segura si no està ocupada ni està amenaçada per cap torre. Per exemple, aquest tauler té tres caselles segures (les tres caselles blanques de la tercera fila començant per dalt):

showmover=false, label=false, maxfield=f4, setpieces=Rf1,Rb4,Rd4,Rd1,Rd3

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n, m i t, seguides de les posicions (fi, ci) de les t torres. Suposeu que n i m estan entre 1 i 40000, que t està entre 1 ‍i ‍100, que les fi estan entre 1 i n, que les ci estan entre 1 i m, i que no hi ha dues torres a la mateixa posició.

Sortida

Per a cada tauler, escriviu el nombre de caselles segures.

Observació

La vostra solució ha de tenir cost menor que O(n · m), tant en temps com en espai.

Public test cases

  • Input

    4 6 5  1 2  1 4  2 4  4 4  4 6
1 1 1  1 1
2 3 1  1 1
2 3 3  1 1  2 3  2 1
200 100 4  1 1  200 1  1 100  200 100

    Output

    3
0
2
0
19404
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++