Tontti

input/code.cpp:235:8: warning: "/*" within comment [-Wcomment]
       }/*
 ^
input/code.cpp: In function 'int main()':
input/code.cpp:57:15: warning: unused variable 'lines' [-Wunused-variable]
  unsigned int lines = 0; //montako lineä on muistissa
               ^
input/code.cpp:178:21: warning: unused variable 'const_size' [-Wunused-variable]
  const unsigned int const_size = min(w, h) - 1; //size on maksimissaa min(leveys - 1, korkeus - 1) = min(leveys, korkeus) - 1
                     ^
input/code.cpp:179:15: warning: unused variable 'cur_const_size' [-Wunused-variable]
  unsigned int cur_const_size;
               ^
input/code.cpp:71: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(Line *pointersToLines[], unsigned int y, unsigned int x, unsigned int cur_size);
bool isOnTheEdgeOfTheArea(const unsigned int x, const unsigned int y);

unsigned int global_w;
unsigned int global_h;

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];	

	unsigned int v = w;
	while(v--) {			
		a->r[v] = 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
		//a->trees_y[v] = 0;	//myöskään ensimmäisen rivin yläpuolella ei ole puita
	}
	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);
		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->last)->isTree[j]) ap->r[j] = 1;	//puu suoraan yläpuolella, joudutaan kasvattamaan kokoa yhdellä jos halutaan saada puu
					else if (ap->isTree[j + 1]) ap->r[j] = 1;	//puu sivulla joudutaan kasvattamaan kokoa yhdellä, jos halutaan saada puu
					else if ((ap->last)->isTree[j + 1]) ap->r[j] = 1;
					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;	//jos molemmat y+1 ja x+1 matkat ovat 0, niin myös tämän matka on nolla, muutoin ... +1
					}
				}
			} else ap->r[j] = 0;
		}
		
		//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)
		
	}
	
	//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;
		while (j--) {	//käydään 'jokainen' alkio läpi
			cur_size = pointersToLines[i]->r[j];
			
			//cout <<  "line: " << i << " " << j << endl;
			
			if (pointersToLines[i]->isTree[j]) count_tree = 1;
			else count_tree = 0; 
			//käydään jokainen size läpi alkaen cur_size:stä ylöspäin
			
			//cur_const_size = min(min(const_size, w - i - 1), h - i - 1);
			if (const_count_tree == 1 && count_tree == 1){
				count_squares++;
			} else if (const_count_tree == 0 && count_tree == 1) ;
			else {
				while (true){
					
					if (!const_count_tree) count_tree += count_trees(pointersToLines, i, j, cur_size);
					
					if (count_tree > const_count_tree){
						//puita on liikaa jo tällä size:llä, joten vaihdetaan alkio seuraavaan ja määritetään
						//sille sitten taas cur_size uudelleen
						
						break;
						//ei tehdä mitään
					}
					
					//cout << i << " " << j << " " << cur_size << " " << count_squares << " " << count_tree << " " << const_count_tree << endl;
				
					//jos puita on oikea määrä
				
					//cout << i << " " << j << " " << count_tree << " " << cur_size << endl;
				
					if (count_tree == const_count_tree) {	//puita on juuri oikea määrä
						
						//lisätään squarejen määrää yhdellä
						//kasvatetaan cur_size:ä yhdellä ja katsotaan pysyykö puiden määrä samana
						//cur_size++;
						//jos uusia puita ei löydy, eli raja-puiden määrä on nolla, 
						//loopataan niin kauan, kunnes:
							//joko löytyy uusia puita tai ollaan reunassa, eli global_wall_value = true;
						
						count_squares++;
						
						//cout << "gotit" << "(" << i << " " << j << ")" << pointersToLines[i]->r[j] << endl;
						
						//loopataan niin kauan kuin ollaan alueella ja puiden määrä ei lisäänny
						/*while (curSize < cur_const_size && !count_trees(pointersToLines, i, j, cur_size) && !isOnTheEdgeOfTheArea(i + cur_size, j + cur_size, h, w))	{
							count_squares++;
							cur_size++;
						}/*
						
						//break;	//poistutaan, sillä tällä indeksillä, alkiolla ei saada enään squareja millä size:llä
						*/
					}
					
					//jos puita on liikaa
					
					
					//jos puita on liian vähän
					//if (count_tree < const_count_tree){
						//kasvatetaan kokoa, ja testataan uudelleen
						//ensin pitää katsoa kuinka paljon kokoa pitää kasvattaa
							//testaa aluksi, että kasvattaa aina vain yhdellä, jos
							//nopeus ei riitä, niin ottaa sitten reunoilta pienimmän luvun,
							//ja kasvattaa sen verran, jos puut ovat harvassa tämä saattaa nopeuttaa ohjelman toimitaa huomattavasti
					//}
					
					cur_size++;	//jos päästään loppuun asti, eli puita oli liian vähän, lisätään kokoa 
					
				}
			}
		}
	}
	
	//cout << endl; printIsTree(ap, w);
	//cout << endl << endl << "Trees:" << count_trees(pointersToLines, 0, 0, 3);

	cout << count_squares;
	
	
	free(char_line);
	//free(pointersToLines);

	return 0;
	
}

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

unsigned int count_trees(Line *pointersToLines[], unsigned int y, unsigned int x, unsigned int cur_size){
	
	//jos ollaan niin reunassa, ettei voi olla kuin joko yksi puu tai ei puita ollenkaan
	if (cur_size == 0) {
		return 0;	// 1 tai 0
	}
	
	//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
	
	
	//tapa 2
	//x, x + cur_size
	//y, y + cur_size
										//(i, j)
	/*int i = cur_size + 1;	//-> esim. cur_size = 2. i = {2, 1, 0}
	unsigned int tree_count = 0;
	
	const unsigned int const_x = x + cur_size;
	const unsigned int const_y = y + cur_size;
	
	while(i--) {	//cur_size:stä nollaan, eli samalle tasolle, missä ollaan
		//jos löytyy puu, lisätään puiden määrää yhdellä
		//pidetään aluksi x vakiona:(liikutaan pysty-suunnassa)
		if (pointersToLines[y]->isTree[const_x]) tree_count++;
		
		//pidetään sitten y vakiona:(liikutaan vaaka-suunnassa)
		if (pointersToLines[const_y]->isTree[x]) tree_count++;
		
	} */
	
	//return tree_count;
	
}

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);
	} while(line->last != NULL);
}

Test 1

Group: 1

Verdict: TIME LIMIT EXCEEDED

Test 2

Group: 1

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 1

Verdict: TIME LIMIT EXCEEDED

Test 4

Group: 1

Verdict: TIME LIMIT EXCEEDED

Test 5

Group: 1

Verdict: TIME LIMIT EXCEEDED

Test 6

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED