Pagini recente » Cod sursa (job #1434388) | Cod sursa (job #2378405) | Cod sursa (job #2364363) | Cod sursa (job #2404212) | Cod sursa (job #437212)
Cod sursa(job #437212)
//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;
}