# PBinfo #3374 – caroiaj – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: andrei

## Enunț

Se consideră un caroiaj format din n linii și n coloane, fiecare element din caroiaj fiind o literă mică din alfabetul englez. Să se constuiască șirul de caractere obținut prin parcurgerea caroiajului pe chenare dinspre exteriorul spre interiorul caroiajului, fiecare chenar fiind parcurs în sensul arcelor de ceas, pornind din colțul stânga sus al fiecărui chenar. Determinați cea mai lungă secvență de caractere situate pe poziții alăturate în șirul construit, care este simetrică. Dacă există mai multe astfel de secvențe de lungime maximă, se va determina ultima dintre ele.

Cerința
Cunoscând numărul natural n și un caroiaj format din n linii și n coloane de litere mici ale alfabetului englez, să se determine cea mai lungă secvență de caractere situate pe poziții alăturate în șirul construit, care este simetrică. Dacă există mai multe secvențe simetrice de lungime maximă, se va determina ultima dintre ele. 

Date de intrare
Fișierul de intrare caroiaj.in conţine pe prima linie, numărul natural n,iar pe următoarele n linii se află câte n caractere, litere mici ale alfabetului englez.

Date de ieșire
Pe prima linie a fişierului caroiaj.out va fi scrisă ultima secvență simetrică de caractere, de lungime maximă din șirul format prin parcurgerea caroiajului de caractere pe chenare, dinspre exteriorul spre interiorul caroiajului, fiecare chenar fiind parcurs în sensul arcelor de ceas, pornind de la colțul din stânga sus al fiecărui chenar.

Restricții și precizări

1 ≤ n ≤ 500
literele mici din caroiaj aparțin alfabetului englez

Exemplul 1:
caroiaj.in

5
abcde
bceaf
abade
abbad
ffabc  
caroiaj.out

abcdefedcba
Explicație
Șirul de caractere format la parcurgerea caroiajului pe chenare în maniera indicată în text, este: abcdefedcbaffaabceadabbba. Ultima secvență simetrică de lungime maximă este abcdefedcba. 

Exemplul 2:
caroiaj.in

3
abc
def
ghi
caroiaj.out

e
Explicație
Șirul de caractere format la parcurgerea caroiajului pe chenare în maniera indicată în text, este abcfihgde.
Ultima secvență simetrică de lungime maximă este e.

## Cod sursă C++

```cpp
#include <fstream>
using namespace std;
ifstream fin("caroiaj.in");
ofstream fout("caroiaj.out");
char a[501][501], s[250001];
int n, i, j, lg, lgmx, poz, nc, k, x, y;
int main()
{
    fin>>n; ///fin.get();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            fin>>a[i][j];
        ///fin.get();
    }
    nc=n/2+n%2;
    k=0;
    for(int t=1;t<=nc;t++)
    {
        ///1
        x=t;
        for(int i=t; i<= n-t+1; i++)
            s[k++]=a[x][i];
        ///2
        y=n-t+1;
        for(int i=t+1;i<=n-t+1;i++)
            s[k++]=a[i][y];
        ///3
        x=n-t+1;
        for(int i=n-t; i>=t; i--)
            s[k++]=a[x][i];
        ///4
        y=t;
        for(int i=n-t;i>=t+1;i--)
            s[k++]=a[i][y];
    }
    ///fout<<s<<endl;
    for(int i=0;i<k;i++)
    {
        ///cazul I, cand secventa simetrica are 1 element in mijloc
        int st, dr;
        st=i-1, dr=i+1;lg=1;
        while(st>=0 && dr<k && s[st]==s[dr])
        {
            st--, dr++ ;
            lg+=2;
        }
        if(lg>=lgmx)
        {
            lgmx=lg;
            poz=st+1;
        }
        ///cazul II, cand secventa simetrica are 2 elemente in mijloc
        if(s[i]==s[i+1] && i+1<k)
        {
        st=i-1;dr=i+2;lg=2;
        while(st>=0 && dr<k && s[st]==s[dr])
        {
            st--, dr++ ;
            lg+=2;
        }
        if(lg>=lgmx)
        {
            lgmx=lg;
            poz=st+1;
        }
        }
    }
    //fout<<lgmx<<endl;
    for(int i=poz;i<poz+lgmx;i++)
        fout<<s[i];
    fout<<'\n';
    fout.close();
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3374)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3374/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3374/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)