Cod sursa(job #1972051)

Utilizator JakeGyllenhaalJake Gyllenhaal JakeGyllenhaal Data 21 aprilie 2017 16:56:12
Problema A+B Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.78 kb
#include <fstream>
#include <cstdio>
#include <vector>
#define VAL 1005

using namespace std;

struct insula
{
    int l1, c1, l2, c2;
};

insula nr;

int N, M, i, j;
int cnt1, cnt2, k;
int ans1, ans2, mn;
int lin[VAL], col[VAL];
int v[VAL][VAL];
bool ok[VAL][VAL];
vector <insula> A;

int main()
{
    freopen("arhipelag.in", "r", stdin);
    freopen("arhipelag.out", "w", stdout);
    scanf("%d %d", &N, &M);
    for (i=1; i<=N; i++)
      for (j=1; j<=M; j++)
        scanf("%d", &v[i][j]);
    for (i=1; i<=N; i++)
    {
        for (j=1; j<=M; j++)
        {
            if (v[i][j]==1 && ok[i][j]==false)
            {
                nr.l1=nr.l2=i;
                nr.c1=nr.c2=j;
                while (v[nr.l2][j]==1)
                  nr.l2++;
                nr.l2--;
                while (v[i][nr.c2]==1)
                  nr.c2++;
                nr.c2--;
                A.push_back(nr);
                for (cnt1=nr.l1; cnt1<=nr.l2; cnt1++)
                  for (cnt2=nr.c1; cnt2<=nr.c2; cnt2++)
                    ok[cnt1][cnt2]=true;
            }
        }
    }
    for (i=1; i<=N; i++)
    {
        for (k=0; k<A.size(); k++)
        {
            if (A[k].l1>i)
              lin[i]+=A[k].l1-i;
            if (i>A[k].l2)
              lin[i]+=i-A[k].l2;
        }
    }
    for (j=1; j<=M; j++)
    {
        for (k=0; k<A.size(); k++)
        {
            if (A[k].c1>j)
              col[j]+=A[k].c1-j;
            if (j>A[k].c2)
              col[j]+=j-A[k].c2;
        }
    }
    mn=1000000000;
    for (i=1; i<=N; i++)
    {
        for (j=1; j<=M; j++)
        {
            if (v[i][j]==0 && mn>lin[i]+col[j])
            {
                mn=lin[i]+col[j];
                ans1=i;
                ans2=j;
            }
        }
    }
    printf("%d %d\n", ans1, ans2);
    return 0;
}