Cod sursa(job #2436787)

Utilizator urweakurweak urweak Data 7 iulie 2019 09:19:09
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.94 kb
#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("ferma3.in");
ofstream fout("ferma3.out");

const int NMax = 405;
int matrice[NMax][NMax];
int matriceFill[NMax][NMax];
int d[NMax*NMax];
int di[4] = { -1, 1 ,0, 0 };
int dj[4] = { 0, 0, 1, -1 };
int V, N, M, n_zona, maxim = -1, maximul = -1;
int cultura[NMax * NMax];
pair <int, int> Q;

bool OK(int i, int j)
{
	if (i < 1 || j < 1 || i > N || j > M)
		return false;
	if (matriceFill[i][j])
		return false;
	return true;
}

void Fill(int x, int y)
{
	d[n_zona]++;

	matriceFill[x][y] = n_zona;

	for (int i = 0; i < 4; i++)
	{
		int noul_i = x + di[i];
		int noul_j = y + dj[i];
		if (OK(noul_i, noul_j) && matrice[x][y] == matrice[noul_i][noul_j]) Fill(noul_i, noul_j);
	}
}

void celula(int x, int y, int a, int b)
{
	for (int i = 0; i < 4; i++)
	{
		int ni = x + di[i];
		int nj = y + dj[i];
		if (OK(ni, nj) && matrice[x][y] == matrice[a][b])
		{
			int val = d[matriceFill[a][b]] + d[matriceFill[x][y]];
			if (val > maximul)
			{
				maximul = val;
				Q.first = ni;
				Q.second = nj;
				matrice[Q.first][Q.second] = matrice[a][b];
			}
		}
	}
}

void ferma(int x, int y)
{
	for (int i = 0; i < 4; i++)
	{
		int ni = x +  di[i];
		int nj = y + dj[i];
		if (OK(ni, nj)) return celula(ni, nj, x, y);
	}
}

int main()
{
	fin >> V >> N >> M;

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			char c;
			fin >> c;
			matrice[i][j] = (int)c;
		}
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			if (!matriceFill[i][j])
			{
				++n_zona;
				Fill(i, j);
				if (maxim < d[n_zona])
					maxim = d[n_zona];
			}
		}
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
			ferma(i, j);
	}

	if(V == 1)
	fout << maxim;
	else
	{
		fout << Q.first << ' ' << Q.second << endl;
		fout << (char)matrice[Q.first][Q.second];
	}

	return 0;
}