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

mb_kepatlo.cpp

Letöltés: mb_kepatlo.cpp

#include <cstdlib>
#include <cstdio>
#include <algorithm>

#define MAXN 10000

using namespace std;


int get_j(int y, int x);
int get_l(int y, int x);
int get_opt(int y, int x);

int n;
int map[MAXN][MAXN];

void beolvas()
{
    FILE* reader = fopen("be2.txt", "r");
    fscanf(reader, "%d", &n);

    char c;
    fscanf(reader, "%c", &c);

    for(int y=0; y<n; y++)
    {
        for(int x=0; x<n; x++)
        {
            fscanf(reader, "%c", &c);
            if(c=='0')
                map[y][x]=0;
            else
                map[y][x]=1;
        }
        fscanf(reader, "%c", &c);
    }

    fclose(reader);
}

int j_cache [MAXN][MAXN];
int get_j(int y, int x)
{
    if(y>=n || x>=n)
        return 0;

    if(j_cache[y][x]!=-1)
        return j_cache[y][x];

    j_cache[y][x]=(1-map[y][x])+get_j(y, x+1);
    return j_cache[y][x];
}

int l_cache [MAXN][MAXN];
int get_l(int y, int x)
{
    if(y>=n || x>=n)
        return 0;

    if(l_cache[y][x]!=-1)
        return l_cache[y][x];

    l_cache[y][x]=map[y][x]+get_l(y+1, x);
    return l_cache[y][x];
}

int opt_cache [MAXN][MAXN];
bool irany_cache[MAXN][MAXN];

int get_opt(int y, int x)
{
    if(opt_cache[y][x]!=-1)
        return opt_cache[y][x];

    int l=get_opt(y+1, x)+ get_j(y, x+1);
    int j=get_opt(y, x+1) + get_l(y+1, x);


    if(j<l)
        irany_cache[y][x]=true;
    else
        irany_cache[y][x]=false;

    opt_cache[y][x]=min(l, j);
    return opt_cache[y][x];
}

bool nem [MAXN][MAXN];
int main()
{
    beolvas();

    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
        {
            j_cache[i][j]=-1;
            l_cache[i][j]=-1;
            opt_cache[i][j]=-1;
            nem[i][j]=false;
        }

    printf("N: %d\n", n);
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
            printf("%d", map[i][j]);
        printf("\n");
    }

    printf("\nOPT: %d\n\n", get_opt(0, 0));
    int x=0;
    int y=0;

    while(x<n && y<n)
    {
        nem[y][x]=true;
        if(irany_cache[y][x])
            x++;
        else
            y++;
    }

    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
            if(!nem[i][j])
                printf("%d", map[i][j]);
            else
                printf(" ");
        printf("\n");
    }
}