Marsi bányászkodás

A NASA űrközpontja Houstonban kevesebb, mint 200 mérföldre található a Texas állambeli San Antoniótól (a 2005. évi ACM verseny döntőjének a helyszínétől). Ez az a hely, ahol az asztronautákat kiképezik a Hét Törpe Küldetésre, ami a következő óriási ugrás az űrkutatásban. A Mars Odüsszeia program feltárta, hogy a Mars felszíne nagyon gazdag yeyenumban és bloggiumban. Ezek az ásványok fontos alkotóelemei néhány forradalmian új gyógyszernek, de különösen ritkák a Földön. A Hét Törpe Küldetés célja az, hogy ezeket az ásványokat kibányássza és elhozza a Földre.

A Mars Odüsszeia űrszondája azonosított egy ásványokban gazdag téglalap alakú területet a Mars felszínén. A területet cellákra osztjuk, amelyek egy n sorból és m oszlopból álló mátrixot alkotnak, ahol a sorok kelet-nyugat, az oszlopok észak-dél irányúak. A szonda minden celláról meghatározta, hogy mennyi yeyenumot és bloggiumot tartalmaz. Az asztronauták építeni fognak egy yeyenumfinomító gyárat a területtől nyugatra és egy bloggiumfinomító gyárat északra. A feladatod, hogy egy olyan futószalagrendszert tervezz, amellyel a legnagyobb mennyiségű ásványi anyagot lehet kibányászni.

A futószalag kétféle lehet: az első keletről nyugatra, a második délről északra tudja szállítani az ásványi anyagot. Minden cellába egyetlen típusú futószalagot tehetsz, de az bármelyik típusú lehet. Ha két szomszédos cellában azonos típusú futószalag van, akkor azok összekapcsolódnak. Például egy adott cellában kibányászott bloggiumot délről északra tartó futószalagok sorozatán keresztül lehet a bloggiumfinomító gyárba elszállítani.

Az ásványok nagyon instabilak, ezért egyenes úton kell őket a gyárba szállítani, kanyarok nélkül. Ez azt jelenti, hogy ha egy dél-észak típusú cellának az északi szomszédjában egy kelet-nyugati cella van, akkor minden, amit a délről északra tartó szalag szállított, elvész. Az egy adott cellában bányászott ásványokat azonnal szalagra kell rakni (azaz nem kezdhetik az útjukat szomszédos cellában lévő szalagon). Továbbá minden bloggium, amit a yeyenumgyárba szállítunk, elvész, és fordítva.

A programodnak olyan futószalagrendszert kell terveznie, amely maximalizálja az összesen kibányászható ásványi anyag mennyiségét, azaz a yeyenumgyárba szállított yeyenum és a bloggiumgyárba szállított bloggium mennyiségének az összegét.

A bemenet specifikációja

A bemenet számos tesztesetet tartalmaz. Mindegyik egy olyan sorral kezdődik, amely két egész számból áll: a sorok száma (1 ≤ n ≤ 500) és az oszlopok száma (1 ≤ m ≤ 500). A következő n sor tartalmazza az egyes cellákban lévő yeyenum mennyiségét. Minden sorban m egész szám található. Az első sor a legészakibb sor, és minden sorban a legelső szám felel meg az adott sor legnyugatibb cellájának. A számok 0 és 1000 közé esnek. A következő n sor az előző formában írja le a bloggium mennyiségét.

A bemenet vége egy olyan sor, ahol n = m = 0.

A kimenet specifikációja

Minden tesztesethez külön sorba ki kell írnod a maximálisan bányászható ásványok mennyiségét.

Példa bemenet

1. 4 4
2. 0 0 10 9
3. 1 3 10 0
4. 4 2 1 3 
5. 1 1 20 0
6. 10 0 0 0
7. 1 1 1 30
8. 0 0 5 5
9. 5 10 10 10
10. 0 0

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. 98

letöltés szöveges állományként