Letöltés: og_kepatlo.cpp #include <stdio.h> #include <iostream> #include <algorithm> using namespace std; int n; char** a; int** o; int** s; int** t; int** apa; void beolvas(char*); void ok(); void sk(); void tk(); void kiir(); int main() { beolvas("atlo.be1"); ok(); sk(); tk(); kiir(); cout << t[n-1][n-1]; } void beolvas(char* file) { FILE* be = fopen(file, "r"); n=30; a = new char*[n]; for(int i=n-1; i>-1; i--) { a[i] = new char[n]; for(int j=n-1; j>-1; j--) { fscanf(be, "%c", &a[i][j]); } char c; fscanf(be, "%c", &c); } fclose(be); } void ok() { o = new int*[n]; for(int i=0; i<n; i++) { o[i]=new int[n]; } for(int j=0; j<n; j++) { if(a[0][j]=='1') {o[0][j]=1;} else {o[0][j]=0;} } for(int i=1; i<n; i++) { for(int j=0;j<n; j++) { if(a[i][j]=='1') {o[i][j]=o[i-1][j]+1;} else {o[i][j]=o[i-1][j];} } } for(int j=0; j<n; j++) { for(int i=0; i<n; i++) { if(a[i][j]=='1') {o[i][j]--;} } } } void sk() { s = new int*[n]; for(int i=0; i<n; i++) { s[i]=new int[n]; } for(int i=0; i<n; i++) { if(a[i][0]=='0') {s[i][0]=1;} else {s[i][0]=0;} } for(int j=1; j<n; j++) { for(int i=0; i<n; i++) { if(a[i][j]=='0') {s[i][j]=s[i][j-1]+1;} else {s[i][j]=s[i][j-1];} } } for(int j=0; j<n; j++) { for(int i=0; i<n; i++) { if(a[i][j]=='0') {s[i][j]--;} } } } void tk() { t = new int*[n]; for(int i=0; i<n; i++) { t[i]=new int[n]; } apa = new int*[n]; for(int i=0; i<n; i++) { apa[i]=new int[n]; } for(int i=0; i<n; i++) { t[0][i]=0; apa[0][i]=1; t[i][0]=0; apa[i][0]=0; } for(int i=1; i<n; i++) { for(int j=1; j<n; j++) { if((t[i][j-1]+o[i][j])>(t[i-1][j]+s[i][j])) { t[i][j]=(t[i-1][j]+s[i][j]); apa[i][j]=0; } else { t[i][j]=(t[i][j-1]+o[i][j]); apa[i][j]=1; } } } } void kiir() { int x=n-1; int y=n-1; a[x][y]= ' '; while((x!=0) || (y!=0)) { if(apa[x][y]==0) { x--; } else { y--; } a[x][y]= ' '; } for(int i=n-1; i>-1; i--) { for(int j=n-1; j>-1; j--) { cout << a[i][j]; } cout << "\n"; } } |