1940 - Bomba

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 bombain.txt 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 bombaout.txt 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 ⩽ 1.000
• 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

Intrare

bombain.txt

4 4

0010

0000

0001

0001

Ieșire

Datele de intrare corespund restricțiilor impuse

bombaout.txt

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 2

Intrare

bombain.txt

3 3

010

001

000

Ieșire

Datele de intrare corespund restricțiilor impuse

bombaout.txt

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.

Exemplul 3

Intrare

bombain.txt

3001 3

010

001

000

Ieșire

Datele de intrare NU corespund restricțiilor impuse

Rezolvare

#1940 - Bomba

def validare_date(n, m, harta):
    if not (1 <= n <= 1000 and 1 <= m <= 1000):
        return False

    if len(harta) != n:
        return False

    for linie in harta:
        if len(linie) != m:
            return False
        if not all(caracter in {'0', '1'} for caracter in linie):
            return False

    return True


def gaseste_pozitie_bomba(n, m, harta):
    for coloana in range(m):
        for linie in range(n):
            if harta[linie][coloana] == '1':
                return linie + 1, coloana + 2


with open("bombain.txt", "r") as fin:
    n, m = map(int, fin.readline().split())
    harta = [fin.readline().strip() for _ in range(n)]

    if validare_date(n, m, harta):
        print("Datele de intrare corespund restricțiilor impuse")

        x, y = gaseste_pozitie_bomba(n, m, harta)

        with open("bombaout.txt", "w") as fout:
            fout.write(f"{x} {y}\n")
    else:
        print("Datele de intrare NU corespund restricțiilor impuse")
        exit(0)