Blokirana polja (polja na koja ne možemo staviti dio broda) nisu samo ona koja su već zauzeta, nego i njima susjedna polja (zbog uvjeta o dodirivanju). Ako znamo sva polja koja su u ovom smislu blokirana, ne moramo više paziti na dodirivanje, nego samo na to da stavimo brod na \(K\) uzastopnih neblokiranih polja.

Načinit ćemo stoga novu ploču, u kojoj ćemo staviti prepreke ne samo na mjesta koja su zauzeta u originalnoj ploči, nego i na njima susjedna polja. Da bismo to učinili, moramo biti u stanju za svako zauzeto polje originalne ploče pronaći njegove susjede (kojih može biti osam, ili manje ako je polje na rubu). Kako to na jednostavan način učiniti? Za polje (redak, stupac) kandidati su za susjede sljedeći:

(redak - 1, stupac - 1)
(redak, stupac - 1)
(redak + 1, stupac)
(redak - 1, stupac)
(redak, stupac + 1)
(redak + 1, stupac + 1)
(redak - 1, stupac + 1)
(redak + 1, stupac - 1)

Za svako od ovih polja valja provjeriti je li unutar ploče (tj. jesu li mu koordinate veće od nule i ne premašuju \(R\) odnosno \(S\)); ako jest, valja ga u novoj ploči označiti blokiranim. Pisanje svih ovih uvjeta naporno je i komplicirano. Srećom, posao možemo veoma skratiti. U tome će nam pomoći dva pomoćna niza:

pomak_retka = (-1, -1, -1, 0, 0, 1, 1, 1),
pomak_stupca = (-1, 0, 1, -1, 1, -1, 0, 1).

For-petljom proći ćemo varijablom smjer od \(1\) do \(8\) te za svaki takav smjer izračunati:

redak_susjeda = redak + pomak_po_retku[smjer],
stupac_susjeda = stupac + pomak_po_stupcu[smjer].

Ako malo razmislite, vidjet ćete da na ovaj način stvarno biramo svih osam gore navedenih susjeda. Unutar petlje još valja provjeriti spomenute uvjete.

Nakon ovoga postupka zanima nas na koliko načina možemo zauzeti \(K\) uzastopnih neblokiranih polja u novoj ploči.

Postavljamo li brod vodoravno, odabrat ćemo sva moguća početna polja broda (redak, stupac) i potom, for-petljom za \(k\) od \(0\) do \(K - 1\), provjeriti je li polje (redak, stupac + k) unutar ploče i je li blokirano. Ako nijedno od tih \(K\) polja nije blokirano, rješenje povećavamo za jedan jer brod možemo postaviti na ovaj način.

Za okomiti smjer činimo posve jednako, osim što provjeravamo polja (redak + k, stupac). Za jednomotorac okomiti smjer ne valja provjeravati jer taj brod zauzima samo jedno polje.

Rješenje

POMAK_RETKA := [-1, -1, -1, 0, 0, 1, 1, 1];
POMAK_STUPCA := [-1, 0, 1, -1, 1, -1, 0, 1];
ulaz(R, S);
ulaz(ploca); // dvodimenzionalno polje znakova
ulaz(K);

za redak := 1 do R činiti
    za stupac := 1 do S činiti
        ako je ploca[redak][stupac] = ‘#’ onda
        {
            ploca2[redak][stupac] := ‘#’;
            za smjer := 1 do 8 činiti
            {
                redak_susjeda := redak + POMAK_RETKA[smjer];
                stupac_susjeda := stupac + POMAK_STUPCA[smjer];
                ako redak_susjeda >= 1 i redak_susjeda <= R i stupac_susjeda >= 1 i stupac_susjeda <= S onda
                    ploca2[redak_susjeda][stupac_susjeda] := ‘#’;
            }
        }
rjesenje := 0;
za redak := 1 do R činiti
    za stupac := 1 do S činiti
    {
        slobodnih := 0;
        za k := 0 do K - 1 činiti
            ako je stupac + k <= S i ploca2[redak][stupac + k] <> ‘#’
                slobodnih := slobodnih + 1;
        ako je slobodnih = K onda
            rjesenje := rjesenje + 1;
        slobodnih := 0;
        za k := 0 do K - 1 činiti
            ako je redak + k <= R i ploca2[redak + k][stupac] <> ‘#’
                slobodnih := slobodnih + 1;
        ako je slobodnih = K i K <> 1 onda
            rjesenje := rjesenje + 1;
    }
izlaz(rjesenje);