[TEMA] Plasare crocodili si elefanti

Salut, incerc sa rezolv aceasta problema insa obtin doar 60p.

Codul meu:

#include <fstream>
 
using namespace std;

ifstream fin("croco1.in");
ofstream fout("croco1.out");

#define DIM 101

int n, m, a[DIM][DIM], cntC1, cntC2, cntE1, cntE2;
char c[DIM][DIM];

void Read();
void Problem();

int main()
{
	Read();
	Problem();
	fin.close();
	fout.close();
	return 0;
}
void Problem()
{
	for ( int i = 1; i <= n; ++i )
		for ( int j = 1; j <= m; ++j )
		{
			if ( i % 2 && j % 2 && !a[i][j] ) c[i][j] = 'C', cntC1++, cntE2++;
			else
			if ( i % 2 && !( j % 2) && !a[i][j] ) c[i][j] = 'E', cntE1++, cntC2++;
			else
			if ( !( i % 2) && j % 2 && !a[i][j] ) c[i][j] = 'E', cntE1++, cntC2++;
			else
			if ( !( i % 2) && !( j % 2) && !a[i][j] ) c[i][j] = 'C', cntC1++, cnt E2++;
			else
			if ( a[i][j] ) c[i][j] = 'A';
		}
	if ( cntC1 > cntC2 )
		fout << cntC1 << ' ' << cntE1 << '\n';
	else
		fout << cntC2 << ' ' << cntE2 << '\n';
}
void Read()
{
	fin >> n >> m;
	for ( int i = 1; i <= n; ++i )
		for ( int j = 1; j <= m; ++j )
			fin >> a[i][j];
}

Cunoaste cineva o cale mai luminoasa care sa tinda spre punctajul maxim?

Pune-i pe toti la un loc. Crocodilii se duc singuri in apa.

1. Trebuie sa stii sa detectezi fiecare regiune de uscat in parte.
2. Fiecare regiune trebuie colorata cu alb sau negru. (De ce nu direct C si E?!).
3. Finalizare.

Pentru exemplele de mai jos, solutia va fi 3,1.

101
000
101

1101
1000
1101

Cy_Cristian, on 28 iulie 2014 - 12:00, said:

Stai, ce?

Ce parte n-ai inteles? Ai incercat macar sa analizezi ce-am spus?
De ce nu poti sa faci mapare direct cu C si E? Ti-am dat si 2 exemple pentru a intelege. Ti-am sugerat alb si negru.

Sa luam o matrice 3x3 cu 2 elemente apa (notate cu 1)

0 0 1
0 1 0
0 0 0

Avem doar 2 metode de a plasa crocodili© si elefanti(E):

1) C E A            
    E A E
    C E C

2) E C A
    C A C
    E C E

In al doilea caz avem cel mai mare nr de crocodili. Pe aceasta metoda m-am bazat in rezolvarea mea, insa nu stiu de ce nu obtin punctajul maxim.

Nu ai prezentat metoda. Cum decizi care va fi modalitatea in care ii vei aranja? Ce elemente de logica te duc la cea de-a 2 aranjare?
Eu ti-am dat un algoritm care te ajuta sa identifici numarul maxim. Cu un foarte mic efort, se poate deduce si o aranjare cu numar maxim de crocodili (de remarcat ca pot fi mai multe astfel de aranjari).

Metoda mea se bazeaza pe faptul ca incepem din coltul stanga sus cu un crocodil sau cu un elefant, iar acele if-uri verifica sa fie o distanta intre 2 animale de acelasi tip. In functie de cazul in care avem numar maxim de crocodili, afisam numarul respectiv si numarul de elefanti.
Nu am inteles ideea pe care ai incercat sa mi-o prezinti.

A programa inseamna a gasi un algoritm care se poate demonstra riguros. Chiar daca uneori se ajunge la magic numbers (cauta pe net si vezi ce zic).
Iti dau un test altfel. Si poate te gandesti ce vreau sa zic cu regiuni in parte.

01101
11000
11101

Daca punem C in coltul din stanga sus, si respectam conditia de a pune din 2 in 2, atunci avem

C11E1
11ECE
111E1

Nu convine
Plecand cu E obtinem:

E11C1
11CEC
111C1

Insa nici unul din cazuri nu convine.
Solutia corecta este:

C11C1
11CEC
111C1

Adica pentru fiecare regiune in parte trebuie sa gasim distributia corecta.
Dar n-o stim de la inceput si pentru a nu face 2 parcurgeri, calculam pentru fiecare regiune in parte numarul de patrate albe si negre. Care sunt cele mai multe reprezinta crocodilii.

Edited by Cy_Cristian, 28 July 2014 - 17:39.

Redount2k9, on 28 iulie 2014 - 11:15, said:

DE CE?
Ai date gresite sau depasesti timpul?

Raspuns gresit.

Ti-am dat un test pe care sa-l incerci.
Pot sa-ti dau unul si mai simplu.

0 1 1 0

Testeaza pe acest caz si vezi unde-i problema de logica.

Am inteles unde e problema de logica. Acum ma gandesc la impartirea pe sectoare a matricei.

incearca sa pui cel putin 4 crodili in jurul fiecarui lac.

Cum?

MarianG, on 28 iulie 2014 - 20:09, said:

cum adica cel putin 4 crocodili? Pai in jurul unui lac poti sa pui maxim 4 crocodili.

Eu as face o functie recursiva care sa se autoapeleze pana cand nu mai exista niciun spatiu uscat in matrice. Iar pentru numararea spatiilor uscate as face o functie, care dupa ce gaseste un singur spatiu uscat returneaza o valoare care indica ca mai exista (nu conteaza numarul lor). Iar in functia recursiva daca mai exista loc uscat atunci parcurgi matricea si unde gasesti apa sau elefant incerci sa pui numarul maxim de crocodili (adica 4), iar dupa ce ai pus crocodilul in jurul lui pui elefanti si dupa ce ai facut operatiile astea pui functia sa se autoapeleze.

Legenda:
P - pamant
A - apa
C - crocodil
E - elefant

0 C E C  0
C A A A  C
0 C E C 0

A A A - este un singur lac, de dimensiune 3

Asa merge. Eu credeam ca tu referi doar la un A.