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.
#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;
}