Rezolvare completă PbInfo #2385 oaste

Enunț

Pe un continent reprezentat printr-o matrice cu n linii și m coloane se află mai multe state, toate în conflict. Astfel, fiecare si-a mobilizat oastea.
Fiecare element al matricei memorează câte o cifră. Două elemente învecinate pe linie sau pe coloană (nu si pe diagonală) aparțin aceluiași stat și se numesc regiuni.
O poziție (i,j) a unei regiuni din matrice este dată de indicele i de linie și indicele j coloană al elementului din matrice corespunzător acestei regiuni.
O poziție din matrice ce contine cifra 0 este o regiune neutră si nu are soldați, iar poziția ce conține o cifră c nenulă este o regiune ce aparține unui stat și are c soldați.

Cerința

Să se determine numărul maxim de soldați dintr-o regiune a statului care are cei mai mulți soldați, precum și poziția acestei regiuni în matrice (linia și coloana).

Date de intrare

Fișierul de intrare oaste.in conține pe prima linie numerele naturale n si m, iar pe fiecare dintre următoarele n linii conține câte m cifre, separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire oaste.out va conține pe prima linie trei numere separate prin cate un spațiu, reprezentând numărul maxim de soldați dintr-o regiune a statului care are cei mai mulți soldați, respectiv linia și coloana poziției acestei regiuni in matrice.

Restricții și precizări

  • n si m vor fi numere naturale cu valori intre 1 si 100 inclusiv;
  • fiecare element al matricei va avea valori naturale cuprinse intre 0 si 9 inclusiv;
  • există cel puțin o cifră nenula în matrice
  • spunem ca un stat are coordonatele (i,j) în matrice dacă regiunea din poziția (i,j) aparține acestui stat și este regiunea cu cea mai mică poziție în sens lexicografic dintre regiunile statului.
  • perechea (i,j) este mai mică în sens lexicografic ca perechea (x,y) dacă i<x sau dacă i=x și j<y
  • dacă există două state cu același număr de soldați și același număr maxim de soldați într-o regiune, se va lua în considerare regiunea cu cea mai mică poziție din statul cu coordonatele cele mai mici în sens lexicografic

Exemplul 1:

oaste.in

4 6
0 1 1 0 2 5
9 0 2 0 1 0
0 1 1 0 0 2
0 0 1 1 1 1

oaste.out

2 2 3

Explicație

Harta din fișierul de intrare contine 3 state. Statul cu culoarea rosie in imagine are cei mai multi soldati iar regiunea din pozitia (2,3) are cei mai multi soldati referitor la celelalte regiuni din acest stat.


desen

Exemplul 2:

oaste.in

4 6
0 1 1 1 1 1
0 0 0 0 0 1
2 2 2 0 0 2
0 0 2 0 0 0
2 3 6

Explicație


Harta din fișierul de intrare contine 2 state, ambele având câte 8 soldați. Regiunea cu număr maxim de soldați luată în considerare este cea din statul cu coordonatele (1,2). Poziția acestei regiuni este (3,6).
Exemplu propus de Tompea Viorel


img2

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema oaste:

#include <fstream>
#include <iostream>
using namespace std;
ifstream f("oaste.in");
ofstream g("oaste.out");

int a[105][105],n,m,s,smax=0,I,J,Imax,Jmax,nrmax,nr,pozi,pozj,pozimax,pozjmax;

void citeste()
{
    f>>n>>m;
    int i,j,x;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
        {
            f>>x;
            a[i][j]=x;
        }
}
void bordare()
{
    for(int j=0; j<=m+1; j++) a[0][j]=a[n+1][j]=0;
    for(int i=0; i<=n+1; i++) a[i][0]=a[i][m+1]=0;
}

void fill(int i, int j)
{
    if(nr<a[i][j])
    {
        nr=a[i][j];
        pozi=i;
        pozj=j;
    }
    else
        if(nr == a[i][j])
        {
            if(pozi > i)
                pozi = i, pozj = j;
            else
                if(pozi == i && pozj > j)
                    pozj = j;
        }
        
    s=s+a[i][j];
    a[i][j]=a[i][j]*(-1);
    if(a[i-1][j]>0)fill(i-1,j);
    if(a[i][j+1]>0)fill(i,j+1);
    if(a[i+1][j]>0)fill(i+1,j);
    if(a[i][j-1]>0)fill(i,j-1);
}
int main()
{
    citeste();
    bordare();
    int i,j;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            if(a[i][j]>0)
            {
                s=0;
                nr=0;
                pozi=i;
                pozj=j;
                I=i;
                J=j;
                fill(i,j);
                if(smax<s)
                {
                    smax=s;
                    Imax=I;
                    Jmax=J;
                    nrmax=nr;
                    pozimax=pozi;
                    pozjmax=pozj;
                }
            }
    g<<nrmax<<" "<<pozimax<<" "<<pozjmax;

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #2385 oaste

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2385 oaste de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!