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.

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.

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

#include <bits/stdc++.h>
using namespace std;

ifstream cin("oaste.in");
ofstream cout("oaste.out");

int a[102][102] , b[102][102];

void fill(int i , int j , int &c)
{
    if(a[i][j]!=0)
    {
        c+=a[i][j];
        a[i][j]=0;
        if(a[i+1][j]!=0)
            fill(i+1 , j , c);
        if(a[i-1][j]!=0)
            fill(i-1 , j , c);
        if(a[i][j-1]!=0)
            fill(i , j-1 , c);
        if(a[i][j+1]!=0)
            fill(i , j+1 , c);
    }
}

int ifi=0 , jfi=0;

void fill1(int i , int j , int &max)
{
    if(b[i][j]!=0)
    {
        if(b[i][j]>max)
            max=b[i][j] , ifi=i , jfi=j;
        if(b[i][j]==max)
        {
            if(i < ifi)
                ifi=i , jfi=j;
            if(i == ifi && j < jfi)
                jfi=j;
                
        }
        b[i][j]=0;
        if(b[i+1][j]!=0)
            fill1(i+1 , j , max);
        if(b[i-1][j]!=0)
            fill1(i-1 , j , max);
        if(b[i][j-1]!=0)
            fill1(i , j-1 , max);
        if(b[i][j+1]!=0)
            fill1(i , j+1 , max);
    }
}

void fill2(int i , int j)
{
    if(b[i][j]!=0)
    {
        b[i][j]=0;
        if(b[i+1][j]!=0)
            fill2(i+1 , j);
        if(b[i-1][j]!=0)
            fill2(i-1 , j);
        if(b[i][j-1]!=0)
            fill2(i , j-1);
        if(b[i][j+1]!=0)
            fill2(i , j+1);
    }
}

int main()
{
    int n , m;
    cin >> n >> m;
    int cnt=0;
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)
            cin >> a[i][j] , b[i][j]=a[i][j];
    int max=0 , lmax=0;
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)
            if(a[i][j]!=0)
            {
                cnt++;
                int c=0;
                fill(i , j , c);
                if(c > max)
                    max = c , lmax=cnt;
            }
    max=0;
    cnt=0;
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)
            if(b[i][j]!=0)
            {
                cnt++;
                if(cnt==lmax)
                {
                    fill1(i , j , max);
                    break;
                }
                else
                    fill2(i , j);
            }
    cout << max << ' ' << ifi << ' ' << jfi;
    return 0;
}