Imagine

[•visanr]

Problema este aceasta: http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=771
Am facut cu divide et impera si am construit si sirul compresat ( nu era necesar, dar mi-a fost mai usor sa vad daca face bine)
Rezolvarea este aceasta:

Cod:

#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;


int m[260][260], n;
vector<int> sol;

void solve(int lmin, int cmin, int lmax, int cmax)
{
     int i, j, app[2];
     for(i = 0; i < 2; i++) app[i] = 0;
     for(i = lmin; i <= lmax; i++)
           for(j = cmin; j <= cmax; j++)
                 app[m[i][j]] ++;
     if(app[0] && !app[1]) 
     {
               sol.push_back(0);
               sol.push_back(0);
     }
     if(app[1] && !app[0])
     {
                sol.push_back(0);
                sol.push_back(1);
     }
     if(app[1] && app[0])
     {
               sol.push_back(1);
               int line = (lmin + lmax) / 2, column = (cmin + cmax) / 2;
               solve(line + 1, cmin, lmax, column);                 // A
               solve(lmin, cmin, line, column);                       // B
               solve(line + 1, column + 1, lmax, cmax);           // C
               solve(lmin, column + 1, line, cmax);                 // D 
     }  
}

int main()
{
    freopen("imagine.in", "r", stdin);
    freopen("imagine.out", "w", stdout);
    int i, j;
    scanf("%i", &n);
    for(i = 1; i <= n; i++)
          for(j = 1; j <= n; j++)
                scanf("%i", &m[i][j]);
    solve(1, 1, n, n);
    printf("%i\n", sol.size());
    return 0;
}

Cu aceasta rezolvare iau 60 de pct, 3 WA si un KBS 6. Imi puteti spune si mie va rog care ar fi problema de primesc WA?



LE: varianta recursiva aduce tot 60 de pct, doar ca am scapat de KBS 6.