Purvam ir taisnstūra forma. Lai purvu būtu vieglāk apsaimniekot, tas ir sadalīts kvadrātveida rūtiņās, kur katras rūtiņas malas garums ir viena vienība. Līdz ar to viss purvs ir sadalīts r rindās un k kolonnās. Kolonnas ir numurētas Rietumu-Austrumu virzienā ar naturāliem skaitļiem no 1 līdz k pēc kārtas. Rindas ir numurētas Ziemeļu-Dienvidu virzienā ar naturāliem skaitļiem no 1 līdz r pēc kārtas. Katrā rūtiņā var būt vai nu cinis(sauszeme) vai akacis(ūdens). Ir nepieciešams izveidot nepārtrauktu ceļu no purva ziemeļu malas (1.rindas) līdz dienvidu malai (r-tajai rindai). Pārvietoties drīkst tikai pa ciņiem, katrā solī pārejot uz tādu cini, kam ar doto ir vismaz viens kopīgs punkts. Akaci var pārvērst par cini, ar izpletni nometot tajā pontonu. Tā kā pontonu nomešana ir dārga, nepieciešams izmantot pēc iespējas mazāk pontonu. Katrā purva rindā, kolonnā vai diagonālē nedrīkst atrasties vairāk par vienu pontonu.
Uzrakstiet programmu, kas dotam akaču un ciņu izvietojumam nosaka mazāko nepieciešamo pontonu skaitu!
Teksta faila akacis.in pirmajā rindā doti divi naturāli skaitļi r un k - purva rūtiņu rindu un kolonnu skaits (1<=r,k<=100). Katrā no nākošajām r faila rindām dots vienas purva rindas apraksts un satur k skaitļus. j-tais skaitlis faila i+1-ajā rindā ir 1, ja purva rūtiņā, kas atrodas i-tās rindas j-tajā kolonnā ir akacis, vai 0, ja cinis.
Teksta faila akacis.out vienīgajā rindā jāizvada naturāls skaitlis - mazākais nepieciešamais pontonu skaits.
| akacis.in | akacis.out |
8 9 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 |
2 |
Piezīme: Pontonus jānomet trešās rindas piektajā kolonnā un septītās rindas astotajā kolonnā.