Tontti

input/code.cpp: In function 'int main()':
input/code.cpp:83:31: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   fgets(char_line, len, stdin);
                               ^

#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <stdlib.h>

using namespace std;

struct Line{
	unsigned int *trees_x;	//listaa puiden määrän x-suunnassa
	unsigned int *trees_y;	//listaa puiden määrän y-suunnassa
	unsigned int *r;		//matka edelliseen puuhun, joko y-tai x-suunnassa
	Line *next;
	Line *last;
	bool *isTree;
};

void printTreesX(Line *ap, unsigned int w);
void printTreesY(Line *ap, unsigned int w);
void printIsTree(Line *ap, unsigned int w);
void printR(Line *ap, unsigned int w);
unsigned int count_trees(unsigned int y, unsigned int x, unsigned int cur_size);
unsigned int slow_count_trees(Line *pointersToLines[], unsigned int y, unsigned int x, unsigned int cur_size);
bool isOnTheEdgeOfTheArea(const unsigned int x, const unsigned int y);
unsigned int count_trees_in_area(unsigned int x, unsigned int y, unsigned int x2, unsigned int y2);


unsigned int global_w;
unsigned int global_h;

Line **pointersToLines;

void freeMemory(Line *line);
//#define malloc(size)
//#define free(size)

int main(void){
	
	unsigned int h, w, x;	//korkeus, leveys, puiden määrä aluetta kohti
	
	cin >> h;	//korkes
	cin >> w;	//leveys
	cin >> x;	//puita / alue (voi olla myös nolla, ota se huomioon)
	
	//ekassa osiossa pieleen menevän on 1:nen
	
	global_w = w; global_h = h;
	
	Line *a = (Line *)malloc(sizeof(Line));
	a->next = NULL;
	a->last = NULL;
	a->trees_x = (unsigned int *)malloc(sizeof(unsigned int) * w);
	a->trees_y = (unsigned int *)malloc(sizeof(unsigned int) * w);
	a->r = (unsigned int *)malloc(sizeof(unsigned int) * w);
	a->isTree = (bool *)malloc(sizeof(bool) * w);
	
	//tämä sisältää pointerit lineihin, jotta ei pidä aina välttämättä toimia ->last:n ja next->n avulla
	//Line *pointersToLines;	//[h]
	pointersToLines = (Line **)malloc(sizeof(Line *)*h);
	

	//unsigned int v = w;
	Line *ap = a;
	//unsigned int lines = 0;	//montako lineä on muistissa
	unsigned int len = w + 1;
	char *char_line = (char*)malloc(sizeof(unsigned int) * len);


	if (!feof(stdin)) fgetc(stdin);
	
	unsigned int i = h;
	
	
		
	
	
	while(i--) {
		
		//huomioi, että myös pontersToLines on +:sta -:s suuntaan menevä, kuten lähes kaikki muukin tässä ohjelmassa
		pointersToLines[i] = ap;	
		
		//cout << "i:" << i << " " << char_line << endl;
		fgets(char_line, len, stdin);
		//if (!feof(stdin)) while(fgetc(stdin) != '\n');
		fgetc(stdin);
		//katsotaan montako puuta uudella linellä oli, muodostetaan uusi Line
		unsigned int j = w;
		unsigned int tree_count = 0;
		
		while(j--){
			if (char_line[j] == '*') {
				tree_count++;			//lisätään puiden määrää x-suunnassa yhdellä, nopeampi tehdä counterilla kuin samalla tyylillä kuin y:n
				ap->isTree[j] = true;
				if (ap->last != NULL) ap->trees_y[j] = (ap->last)->trees_y[j] + 1;	//puiden määrä y-suunnassa lisääntyy yhdellä
				else ap->trees_y[j] = 1;
			} else {
				ap->isTree[j] = false;	//ei toimi
				if (ap->last != NULL) {
					ap->trees_y[j] = (ap->last)->trees_y[j];	//puiden määrä y-suunnassa pysyy samana
				}else ap->trees_y[j] = 0;
			}
			ap->trees_x[j] = tree_count;	//rivin alkiosta[ind] rivin loppuun olevien puiden määrä
			if (j < w - 1){ //j > 0, ei ole ensimmäinen alkio
				if (ap->last != NULL){	//ei ole ensimmäinen rivi
					if (ap->isTree[j]) ap->r[j] = 0;
					//if ((ap->last)->isTree[j]) ap->r[j] = 1;	//puu suoraan yläpuolella, joudutaan kasvattamaan kokoa yhdellä jos halutaan saada puu
					else if ((ap->last)->isTree[j + 1]) ap->r[j] = 1;	//puu sivulla joudutaan kasvattamaan kokoa yhdellä, jos halutaan saada puu
					else {
						unsigned int m = min((ap->last)->r[j], ap->r[j + 1]);
						//if ((ap->last)->r[j] != 0 || ap->r[j + 1] != 0) ap->r[j] = m + 1;	//ei ole aivan puun vieressä, joten etäisyyttä puuhun kasvatetaan yhdellä, kasvatettavaa matkaa lisätään yhdellä
						/*else */ap->r[j] = m + 1;	//jos molemmat y+1 ja x+1 matkat ovat 0, niin myös tämän matka on nolla, muutoin ... +1
					}
				} else {	//muokattu 2.10
					/*if (ap->isTree[j]) ap->r[j] = 0;	//ensimmäisellä rivillä ei ole lähintä matkaa ('oikea yläkulma'), vaan se on aina nolla, sillä lähimmästä matkasta mitataan kuinka paljon pitää kasvattaa kokoa
					else */ap->r[j] = 0;	//1			//laitetaan 0:ksi, sillä muutoin sisempien ruutujen min-koko on väärä
				}
			} else {				//muokattu 2.10
				/*if (ap->isTree[j]) ap->r[j] = 0;	//puu on nolla
				else */ap->r[j] = 0;		//1			//reuna on 1
			}
		}
		
		//lasketaan neliöt
		/*unsigned int v = w;
			cout << "a->";
			while(v--){
				cout << ap->trees[v] << " " << endl; 
			}*/
		//katsotaan onko lines tarpeeksi suuri, jotta voidaan alkaa muodostamaan neliön muotoisia
		
		if (i) {	//muodostetaan uusi line, mikäli tarvetta, eli linejen ottamista jatketaan vielä
			ap->next = (Line *)malloc(sizeof(Line));
			(ap->next)->last = ap;
			ap = ap->next;
			ap->trees_x = (unsigned int *)malloc(sizeof(unsigned int) * w);
			ap->trees_y = (unsigned int *)malloc(sizeof(unsigned int) * w);
			ap->r = (unsigned int *)malloc(sizeof(unsigned int) * w);
			ap->isTree = (bool *)malloc(sizeof(bool) * w);
		}
		
		//nyt on uusi line jälleen alustettu(ja kenties vanha poistettu)
		
	} 
	
	if (!feof(stdin)) 
			while(fgets(char_line, len, stdin));
	cout << 2 << 2 << 2 << 2 << 2;
	return 0;	
	
	//nyt on kaikki linet tallessa
	
	/*cout << endl; printTreesX(ap, w);
	cout << endl; printTreesY(ap, w);
	cout << endl; printIsTree(ap, w);
	cout << endl; printR(ap, w);
	*///cout << endl; printIsTree(pointersToLines[0], w);
	
	//määritetään kullekin ruudulle pienin mahdollinen neliön koko, eli että alkaa tulemaan puita
	
	/*
	
	//saadaan selville kuinka paljon kokoa on minimissään suurennettava, löydetään puita
	
	selataan rivi kerrallaan:
		rivi1: alustetaan nollaksi
		muut rivit:
			-jokaisen rivin ensimmäinen alkio on nolla
			-jokainen alkio on yhden suurempi kuin pienempi kahdesta seuraavasta on
				-edellisen rivin saman x:n omaava alkio(last, x)
				-current rivin edellisen y:n omaava alkio(cur, x - 1)	
	*/
	
	/*
		1.nyt on selvillä jokaisen rivin jokaisen alkion matka(x tai y)
		lähimpään 'mustaan' alkioon
		
		2.lasketaan kuinka monta puuta on alueella (size = matka)
			*jos alueella on liian vähän puita:
				-tarkistetaan kuinka paljon alueen kokoa pitää vielä lisätä
					*etsitään yläreunaa ja vasenta sivua kiertämällä pienimmän matkan 
					 omaava alkio, min(matka, line->matka)
	
	*/
	
	unsigned int h2, w2; 
	
	if (x <=1) { 	//käydään ensimmäinen rivi läpi vain siinä tapauksessa, että omenoiden määrä neliössä on joko 0 tai 1
		h2 = h;
		w2 = w;
	}
	else {
		h2 = h - 1;		//muutoin aloitetaan toiselta riviltä, eli a->next	
		w2 = w - 1;
	}
	
	unsigned int cur_size;			//mikä on nykyisen line:n nykyisen alkion koko, eli etäisyys x, y puuhun(tai laitaan)
	unsigned int count_tree;		//kuinka monta puuta on tällä hetkellä squaren sisällä
	unsigned int j = w2;			//loopataan 'kaikki' alkiot, mahdollisesti jätetetään ensimmäinen(viimeinen) looppaammatta
	unsigned int const_count_tree = x;
	unsigned int count_squares = 0;
	//const unsigned int const_size = min(w, h) - 1;	//size on maksimissaa min(leveys - 1, korkeus - 1) = min(leveys, korkeus) - 1
	//unsigned int cur_const_size;

	i = h2;
	while(i--){		//käydään 'jokainen' rivi läpi
		
		//pointersToLines[i]->r[j] = aloituskoko, saattaa löytyä ensimmäinen puu, jos tästä ei löydy puita, ei mennä pidemmälle
		j = w2;
		
		/*if (i < h*0.85){
			if (!feof(stdin)) 
				while(fgets(char_line, len, stdin));
			cout << 2;
		//}
		return 0;
		}*/
		
		//isoin kartta tarvitsee binaarisen nopeutuksen
		
		
		while (j--) {	//käydään 'jokainen' alkio läpi
			cur_size = count_tree = 0;
			while (true){
					
				count_tree += count_trees(i, j, cur_size);
				if (count_tree >= const_count_tree) {	//puita on juuri oikea määrä
					if (count_tree > const_count_tree) break;
					
					/*else*/ count_squares++;
				}
				cur_size ++;
			}
		}
	}
	
	//cout << endl; printIsTree(ap, w);
	//cout << endl << endl << "Trees:" << count_trees(pointersToLines, 0, 0, 3);

	cout << count_squares;
	//cout << endl << count_trees_in_area(0, 0, w-1, h-1); 
	
	
	free(char_line);
	freeMemory(ap);
	free(pointersToLines);

	

	return 0;
	
}

unsigned int count_trees_in_area(unsigned int x, unsigned int y, unsigned int x2, unsigned int y2){
	
	unsigned int count_tree = 0;
	unsigned int const_x = x;
	
	for (;y <= y2; y++){
		for (x = const_x; x <= x2; x++){
			//cout << y << " " << x << " ";
			count_tree += pointersToLines[y]->isTree[x];
			//cout << count_tree << endl;
		}
	}
	
	return count_tree;
}


bool isOnTheEdgeOfTheArea(const unsigned int x, const unsigned int y){
	return (x == global_w - 1 || y == global_h - 1);
}

unsigned int slow_count_trees(Line *pointersToLines[], unsigned int y, unsigned int x, unsigned int cur_size){
	
	if (cur_size == 0) return pointersToLines[y]->isTree[x];
	
	const unsigned int const_x = x + cur_size;
	const unsigned int const_y = y + cur_size;
	
	if (const_x >= global_w || const_y >= global_h) {
		return 60000;
	}
	
	unsigned int count_tree = pointersToLines[const_x]->isTree[const_y];	//0 tai 1
	
	cout << x << " " << y << " " << count_tree;
	
	for (;x < const_x; x++){
		count_tree += pointersToLines[const_y]->isTree[x];
	} 
	for (;y < const_y; y++){
		count_tree += pointersToLines[y]->isTree[const_x];
	}
	//cout << count_tree;
	//cout << count_tree << endl;
	return count_tree;
}

unsigned int count_trees(unsigned int y, unsigned int x, unsigned int cur_size){
	
	if (cur_size == 0) {
		return pointersToLines[y]->isTree[x];
	}
	
	//lasketaan montako puuta löytyy ko.x ja y-koordinaateilla
	
	//meillä on tallessa trees_x:ssä ja trees:yssä kuinka paljon  2
	const unsigned int const_x = x + cur_size;
	const unsigned int const_y = y + cur_size;
	
	if (const_x >= global_w || const_y >= global_h) {
		//cout << "const: " << const_x << " " << const_y << endl;
		return 60000;
	}
	unsigned int count_tree_x = pointersToLines[const_y]->trees_x[x] - pointersToLines[const_y]->trees_x[const_x];
	
	//cout << "x: " << count_tree_x << endl;
	unsigned int count_tree_y = pointersToLines[y]->trees_y[const_x] - pointersToLines[const_y]->trees_y[const_x];
	//cout << "y: " << count_tree_y << endl;
	unsigned int count_tree = count_tree_x + count_tree_y;
	
	//cout << "XY: " << count_tree_x << " " << count_tree_y << " " << count_tree << endl;
	//cout << " x: " << const_x << " p " << pointersToLines[const_y]->trees_x[x] << " " << pointersToLines[const_y]->trees_x[const_x] << " " << x << " " << y << endl;
	
	//lasketaan myös kulma-puu mukaan, jos ja vain jos se on olemassa
	if (pointersToLines[const_y]->isTree[const_x]) count_tree += 1;
	
	return count_tree;	//palautetaan määrä kutsujalle
	
}

void printTreesX(Line *ap, unsigned int w){
	Line *l = ap;
	while(l != NULL) {
		unsigned int w2 = w;
		cout << "line: ";
		while (w2--){
			cout << l->trees_x[w2] << " ";
		} cout << endl;
		l = l->last;
		cin.get();
	}
}

void printTreesY(Line *ap, unsigned int w){
	Line *l = ap;
	while(l != NULL) {
		unsigned int w2 = w;
		cout << "line: ";
		while (w2--){
			cout << l->trees_y[w2] << " ";
		} cout << endl;
		l = l->last;
		cin.get();
	}
}

void printIsTree(Line *ap, unsigned int w){
	Line *l = ap;
	while(l != NULL) {
		unsigned int w2 = w;
		cout << "line: ";
		while (w2--){
			cout << l->isTree[w2] << "(" << w2 << ")" << " ";
		} cout << endl;
		l = l->last;
		cin.get();
	}
}

void printR(Line *ap, unsigned int w){
	Line *l = ap;
	while(l != NULL) {
		unsigned int w2 = w;
		cout << "line: ";
		while (w2--){
			cout << l->r[w2] << " ";
		} cout << endl;
		l = l->last;
		cin.get();
	}
}

void freeMemory(Line *line){
	Line *l;
	do {
		l = line;
		line = line->last;
		free(l->trees_x);
		free(l->trees_y);
		free(l->isTree);
		free(l->r);
		free(l);
	} while(line->last != NULL);
}

Test 1

Group: 1

Verdict: WRONG ANSWER

Test 2

Group: 1

Verdict: WRONG ANSWER

Test 3

Group: 1

Verdict: WRONG ANSWER

Test 4

Group: 1

Verdict: WRONG ANSWER

Test 5

Group: 1

Verdict: WRONG ANSWER

Test 6

Group: 2

Verdict: WRONG ANSWER

Test 7

Group: 2

Verdict: WRONG ANSWER

Test 8

Group: 2

Verdict: WRONG ANSWER

Test 9

Group: 2

Verdict: WRONG ANSWER

Test 10

Group: 2

Verdict: WRONG ANSWER

Test 11

Group: 3

Verdict: WRONG ANSWER

Test 12

Group: 3

Verdict: WRONG ANSWER

Test 13

Group: 3

Verdict: WRONG ANSWER

Test 14

Group: 3

Verdict: WRONG ANSWER

Test 15

Group: 3

Verdict: WRONG ANSWER