Cod sursa(job #437212)

Utilizator angel_pacPetre Andreea Cristina angel_pac Data 9 aprilie 2010 14:48:49
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 3.18 kb
//Petre Andreea Cristina 321CA Tema1 PA problema 1
#include <stdio.h>
#include <stdlib.h>
#include <fstream>
#include<iostream>

using namespace std;
#define INF 12345

fstream f("figuri2.in",ios::in);
fstream g("figuri2.out",ios::out);
 
void patrate( int **a, int n){
	int i, j, aux, max;
	int cnt = 0;
	
	max = -INF;
	//calculez numar de patrate
	for (i = n-2 ; i>=0; i --){      //theta(n^2)
		for( j = n-2; j >=0 ; j--){
			aux = INF;
			if(a[i][j]) {
				aux = a[i][j+1];
				if( a[i+1][j+1] <  aux)
					aux = a[i+1][j+1];
				if( a[i+1][j] <  aux)
					aux = a[i+1][j];
				a[i][j] = aux+1;
				if ( max < a[i][j])
					max = a[i][j];
			}
		}
	}
	//theta(n^2)
	for( i = 0 ; i < n ; i ++ )
		for( j = 0 ;  j < n; j++)
			 if(a[i][j] == max)
				cnt++;

	g<<max<<" "<<cnt<<"\n";
}
 
void romburi( int **a, int n){
 
	int i, j, min, max;
	int cnt = 0;
	
	//matrice intermediare
	int  **sol;
	sol = (int **) calloc (n, sizeof(int*));
	for (i = 0 ; i < n ; i++){
		sol[i] = (int *) calloc(n, sizeof(int));
	}
	//theta(n)
	for( i = 0; i < n; i ++) {
		sol[i][0] = a[i][0];
		sol[0][i] = a[0][i];
		sol[i][n-1] = a[i][n-1];
		sol[0][i] = a[0][i];
		sol[i][0] = a[i][0];
		sol[n-1][i] = a[n-1][i];
		sol[i][n-1] = a[i][n-1];
		sol[n-1][i] = a[n-1][i];
	}
	//theta(n^2)
	for ( i = 1; i < n-1; i++){
		for ( j = 1; j < n-1; j++){
			min = INF;
			if(a[i][j]) {
				min = a[i][j-1];
				if( a[i-1][j] <  min)
					min = a[i-1][j] ;
				a[i][j] = min+1;
				sol[i][j] = min+1;
			}
		}  
	}
 	//theta(n^2)
	for ( i = 1; i < n-1; i++){
		for ( j = n-2; j >0 ; j--){
			min = INF;
			if(a[i][j]) {
				min = a[i-1][j];
				if( a[i][j+1] <  min)
					min = a[i][j+1] ;
				a[i][j] = min+1;
				if ( sol[i][j] > a[i][j] )
					sol[i][j] = a[i][j];
				}
		}  
	}
     	//theta(n^2)
	for ( i = n-2; i >0 ; i--){
		for ( j = 1; j < n-1; j++){
			min = INF;
			if(a[i][j]) {
				min = a[i][j-1];
				if( a[i+1][j] <  min)
					min = a[i+1][j] ;
				a[i][j] = min+1;
				if ( sol[i][j] > a[i][j] )
					sol[i][j] = a[i][j];
			}
		}  
	}
	//theta(n^2)  
	for ( i = n-2; i > 0; i--){
		for ( j = n-2; j > 0; j--){
			min = INF;
			if(a[i][j]) {
				min = a[i][j+1];
				if( a[i+1][j] <  min)
					min = a[i+1][j] ;
				a[i][j] = min+1;
				if ( sol[i][j] > a[i][j] )
					sol[i][j] = a[i][j];
			}              
		}  
	}
	//calculez numar de romburi
     	//theta(n^2)
	max = -INF;
	for ( i = 0; i< n; i++){
		for(j = 0; j < n; j++){
			if( sol[i][j] > max)
				max = sol[i][j];
		}
	}
     
	for( i = 0 ; i < n ; i ++ )
		for( j = 0 ;  j < n; j++)
			if(sol[i][j] == max)
				cnt++;
	   
	g<<max<<" "<<cnt<<"\n";
      
        //eliberez matricea auxiliara
	free(sol);
}
  
int main() {
	int n;
	int **a, *ln, *cn;
	int i, j;
	f>>n;
	a = (int **) calloc (n, sizeof(int*));
	ln = (int *) calloc (n, sizeof(int));
	cn = (int *) calloc (n, sizeof(int));
	char aux;
	//theta(n)
	for (i = 0 ; i < n ; i++)
		a[i] = (int *) calloc(n, sizeof(int));
	//theta(n^2)
	for( i = 0 ; i < n ;i++)
		for(j=0;j<n;j++){
			f>>aux;
			a[i][j] = aux -'0';
		}
	//theta(n)
	for( i = 0; i < n; i ++) {
		cn[i] = a[i][0];
		ln[i] = a[0][i];
	}
	patrate(a, n);
	//theta(n)
	for( i = 0; i < n; i ++) {
		a[i][0] = cn[i];
		a[0][i] = ln[i];
 	}
	romburi(a,  n);
	  
	free(a);   
	
	return 0;
}