Pagini recente » Cod sursa (job #3200438) | Cod sursa (job #3286840) | Cod sursa (job #135918) | Cod sursa (job #1828487) | Cod sursa (job #1972051)
#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;
}