Rezolvare completă PbInfo #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 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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Bomba:

/*
    Proposer: Daniel Rusu
    Solution: O(N^2)
    Score: 100
*/

#include <fstream>
#include <cstring>

using namespace std;

ifstream fin("bomba.in");
ofstream fout("bomba.out");

#define DIM 1002

char Map[DIM][DIM];
int Line[DIM], Col[DIM];
int N, M;

int main() {
    fin >> N >> M;

    int totalEnemies = 0;
    for(int i = 1; i <= N; ++i) {
        fin >> (Map[i] + 1);

        for(int j = 1; j <= M; ++j) {
            if(Map[i][j] == '1') {
                ++Line[i];
                ++Col[j];
                ++totalEnemies;
            }
        }
    }

    for(int i = 1; i <= N; ++i) {
        for(int j = 1; j <= M; ++j) {
            int totalDestroyed = Line[i] + Col[j] - (Map[i][j] == '1');

            if(totalDestroyed == totalEnemies) {
                fout << i << ' ' << j << '\n';
                i = j = N + M;
            }
        }
    }

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #1940 Bomba

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1940 Bomba de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!