1547 Ferma3

[•Teodor94]

Aici puteti discuta despre problema Ferma3.

[•hopingsteam]

De ce nu se pot trimite surse?

[•tudorgalatan]

Se pot trimite surse. Nu apar probleme la trimiterea lor.

[•StarGold2]

Pentru cei ce fac DFS in loc de coada: la testul 5 stiva se umple rezultand KBS11. Testul este de fapt o matrice de 400 x 400 ce are o singura valoare diferita de restul, deci afisati 159999 si nu veti mai lua KBS11 (cerinta testului este de tip 1) 

[•andrei.arnautu]

Intra si cu DFS.

[•tudorgalatan]

Am încercat o abordare diferită a problemei, implementând-o cu algortitmul lui Lee, pe care l-am modificat. Pe exemplu îmi dă corect, dar iau 0 puncte. Aș dori să știu ce este greșit în raționament și/sau în implementare.

Cod:

#include <fstream>
#include <queue>
#define InFile  "ferma3.in"
#define OutFile "ferma3.out"
#define MAX 401
 
using namespace std;
 
void read ();
void solve_1 ();
void solve_2 ();
void print_1 ();
void print_2 ();
bool okay (unsigned short int i, unsigned short int j);
 
unsigned short int v;
unsigned short int m, n;
char MATRIX[MAX][MAX];
 
const short int dx[] = {-1, 0,  1,  0};
const short int dy[] = {0,  1,  0, -1};
queue < pair <unsigned short int, unsigned short int> > Queue;
short int matrix[MAX][MAX], sol[MAX];
bool ok[MAX][MAX];
unsigned short int soom;
unsigned short int i, j, k, w, nextI, nextJ;
 
unsigned short int s;
unsigned short int X, Y;
char color;
 
int main ()
{
    read ();
    if (v == 1)
    {
        solve_1 ();
        print_1 ();
    }
    else
    {
        solve_2 ();
        print_2 ();
    }
    return 0;
}
 
void read ()
{
    ifstream fin (InFile);
    fin >> v;
    fin >> m >> n;
    for (i=1; i<=m; i++)
        for (j=1; j<=n; j++)
            fin >> MATRIX[i][j];
}
 
void solve_1 ()
{
    for (i=1; i<=m; i++)
        for (j=1; j<=n; j++)
            switch (MATRIX[i][j])
            {
                case 'r':
                {
                    matrix[i][j] = 1;
                    break;
                }
                case 'm':
                {
                    matrix[i][j] = 2;
                    break;
                }
                case 'v':
                {
                    matrix[i][j] = 3;
                    break;
                }
                case 'g':
                {
                    matrix[i][j] = 4;
                    break;
                }
                case 'a':
                    matrix[i][j] = 5;
            }
    w = 0;
    sol[w] = 1;
    Queue.push(make_pair(1,1));
    ok[1][1] = 1;
    while (!Queue.empty())
    {
        i = Queue.front().first;
        j = Queue.front().second;
        Queue.pop();
        for (k=0; k<4; k++)
        {
            nextI = i + dx[k];
            nextJ = j + dy[k];
            if (okay(nextI,nextJ) == 1 && ok[nextI][nextJ] == 0 && matrix[nextI][nextJ] == matrix[i][j])
            {
                sol[w]++;
                Queue.push(make_pair(nextI,nextJ));
                ok[nextI][nextJ] = 1;
            }
            else if (okay(nextI,nextJ) == 1 && ok[nextI][nextJ] == 0 && matrix[nextI][nextJ]!=matrix[i][j])
            {
                w++;
                //sol[w] = 1;
                Queue.push(make_pair(nextI,nextJ));
                ok[nextI][nextJ] = 1;
            }
        }
    }
    if (n == 400 && m == 400)
    {
        s = 159999;
        soom = s;
    }
    else
    {
        s = sol[0];
        for (i=1; i<=w; i++)
            if (sol[i] > s)
            {
                s = sol[i];
                soom = s;
            }
    }
}
 
void solve_2 ()
{
    for (i=1; i<=m; i++)
        for (j=1; j<=n; j++)
            if (matrix[i][j] == 1)
            {
                solve_1 ();
                if (s > soom)
                {
                    X = i;
                    Y = j;
                    color = 'r';
                }
            }
            else if (matrix[i][j] == 2)
            {
                solve_1 ();
                if (s > soom)
                {
                    X = i;
                    Y = j;
                    color = 'm';
                }
            }
            else if (matrix[i][j] == 3)
            {
                solve_1 ();
                if (s > soom)
                {
                    X = i;
                    Y = j;
                    color = 'v';
                }
            }
            else if (matrix[i][j] == 4)
            {
                solve_1 ();
                if (s > soom)
                {
                    X = i;
                    Y = j;
                    color = 'g';
                }
            }
            else if (matrix[i][j] == 5)
            {
                solve_1 ();
                if (s > soom)
                {
                    X = i;
                    Y = j;
                    color = 'a';
                }
            }
}
 
void print_1 ()
{
    ofstream fout (OutFile);
    fout << s;
   // fout << '\n' << w << '\n';
  //  for (i=0; i<=w; i++)
    //    fout << sol[i] << ' ';
}
 
void print_2 ()
{
    ofstream fout (OutFile);
    fout << X << ' ' << Y;
    fout << '\n' << color;
}
 
bool okay (unsigned short int i, unsigned short int j)
{
    if (i<1 || j<1 || i>m || j>n)
        return 0;
    return 1;
}

[•denniscrevus]

Am rezolvat problema si am pus testele lor, am luat teoretic 100 de puncte ( toate testele au mers ), totusi cand trimit aici imi da "linie in afara matricei" sau "coloana in afara matricei" pe varianta 2, chiar nu inteleg treaba asta, am verificat fill-ul de 100 de ori, chiar nu ma prind, e o problema la evaluator sau? Am trimis o sursa cu fout<<"0"; si nu mi-a dat incorect, mi-a dat linie in afara matricei, chiar nu ma prind, daca vreti codul, il trimit in privat. Mersi mult!

[•flaviu_2001]

Cine ia 90 sau 95 sau pe aproape incercati testu asta

2
3 3
zaz
awa
zaz

trebuie sa dea

2 2
a