Cerința

Războiul intergalactic a început, iar extratereștrii au invadat deja planeta noastră. Misiunea ta este să salvezi toți locuitorii planetei cât mai repede cu putință!

Într-un hambar vechi, ai găsit un robot proiectat special pentru amplasarea de bombe nucleare și totodată o hartă a planetei sub formă de dreptunghi împărțită în N x M zone pătratice dispuse pe N linii și M coloane, de dimensiune 1. Pe hartă sunt reprezentate și pozițiile extratereștrilor (xi,yi), unde xi reprezintă indicele de linie, iar yi reprezintă indicele de coloană al extraterestrului i. De asemenea, robotul poate amplasa bombe în orice poziție de pe hartă, iar la declanșarea lor, acestea distrug orice extraterestru de pe aceeași linie sau de pe aceeași coloană cu ele.

Din păcate, robotul nu este echipat decât cu o singură bombă. Datoria ta este să-i transmiți robotului coordonatele x y unde să amplaseze bomba, astfel încât toți extratereștrii să fie distruși. Poți să salvezi planeta? Timpul se scurge! Tic, tac, tic, tac…

Date de intrare

Fișierul de intrare bomba.in conține pe prima linie două numere naturale N și M, reprezentând numărul de linii, respectiv numărul de coloane ale hărții. Pe următoarele N linii se găsesc câte M caractere din mulțimea {0,1}; 0 reprezintă o poziție liberă, în timp ce 1 reprezintă o poziție ocupată de un extraterestru.

Date de ieșire

Fișierul de ieșire bomba.out va conține pe prima linie două numere naturale x și y, reprezentând indicele liniei și al coloanei unde trebuie amplasată bomba astfel încât toți extratereștrii să fie distruși.

Restricții și precizări

• 1 ≤ N, M ≤ 1000
• Numărul de extratereștri nu depășește 2000.
• Dacă există mai multe celule în care poate fi amplasată bomba, se alege cea cu indicele de linie x minim. Dacă există mai multe celule în care poate fi amplasată bomba cu indicele de linie x minim, se alege cea cu indicele de coloană y minim.
• Liniile și coloanele hărții sunt numerotate începând cu 1.
• Se garantează că pentru datele de test există întotdeauna soluție.

Exemplul 1

bomba.in

4 4
0010
0000
0001
0001

bomba.out

1 4

Explicație

Bomba trebuie să fie amplasată pe poziția (1,4) astfel încât toți extratereștrii să fie distruși.

Exemplul 1

bomba.in

3 3
010
001
000

bomba.out

1 3

Explicație

Bomba poate să fie amplasată atât pe poziția (2,2), cât și pe poziția (1,3), astfel se afișează cea de-a doua poziție deoarece are indicele de linie X minim.

#include <bits/stdc++.h>
using namespace std;

ifstream cin("bomba.in");
ofstream cout("bomba.out");

int a[1001][1001] , c[1001] , l[1001];

int main()
{
    int n , m , cnt = 0;
    char ch;
    cin >> n >> m;
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)
        {
            cin >> ch;
            if(ch == '0')
                a[i][j]=0;
            else
                a[i][j]=1 , cnt++;
        }
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)
            l[i]+=a[i][j] , c[j]+=a[i][j];
    int x = -1 , y;
    for(int i = 1 ; i <= n && x == -1; ++i)
    {
        for(int j = 1 ; j <= m && x == -1 ; ++j)
        {
            if(c[j] + l[i] - a[i][j] == cnt)
                x = i , y = j;
        }
    }
    cout << x << ' ' << y;
}