Enunțul problemei boats, de clasa a 8-a, dată în 2017 la ONI, se găsește pe PbInfo.

Rezumat boats

Se dă o matrice cu valori din mulțimea {0, 1}. O navă-linie se definește drept o secvență maximală (care nu face parte dintr-una mai mare) de celule cu valoarea 1, aflate pe o linie a matricei date. Similar, o navă-coloană este o secvență maximală de celule cu valoarea 1, dispuse pe o coloană a matricei. Lungimea unei nave este egală cu numărul de celule din componența sa. O navă formată dintr-un singur pătrățel nu este nici linie, nici coloană. Două nave diferite nu se ating pe laturi sau colțuri, nu se suprapun și nu au celule comune. În matricea dată se află doar nave-linie, nave-coloană și nave formate dintr-o singură celulă.

În funcție de cerință (de valoarea lui p), trebuie să determinăm:

  • numărul de nave formate dintr-o singură celulă
  • numărul de nave-linie și de nave-coloană, precum și numărul lor

Soluție boats

Pentru prima cerință se parcurge matricea și pentru fiecare element se testează dacă este 1 și dacă cei patru vecini ai săi (sus, jos, stânga, dreapta) sunt 0. Dacă elementul curent respectă aceste condiții, atunci soluția se incrementează.

A doua cerință este pur și simplu o problemă (destul de simplă) cu secvențe. Se parcurge fiecare linie și fiecare coloană a matricei date și pentru fiecare secvență maximală de 1 găsită, se actualizează soluția corespunzător. Vom avea nevoie de doi vectori de frecvență, lgL și lgC. În lgL[i] se reține numărul de nave-linie de lungime i, iar în lgC[i] numărul de nave-coloană de lungime i.

Sursă C++ boats

Dacă ai vreo nedumerire cu privire la problema boats, lasă un comentariu și te voi ajuta 🙂

Îți place conținutul acestui site?

Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!