Programozás‎ > ‎Feladatok‎ > ‎Képátló‎ > ‎Megoldás‎ > ‎

og_kepatlo.cpp

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";
    }
}