Rezolvare completă PbInfo #1714 Pandora

Anul 2154, undeva pe luxurianta planetă Pandora.

Aici coloniștii RDA (Resources Development Administration) doresc să-și stabilească o bază stelară pentru a exploata rezervele naturale de unobtainium, un minereu rar și prețios aflat din belșug pe munții plutitori (Hallelujah Mountains), munți ce plutesc lent purtați de curenții magnetici asemănător aisbergurilor în mare, pe suprafața planetei formată din gaz lichid.

Pentru prospectarea și exploatarea zăcămintelor de minereu este necesară cartografierea suprafeței planetei și întocmirea unei hărți digitizate reprezentate sub forma unui tablou bidimensional. Astfel, regiunea de interes geologic este împărțită în NxN pătrate teritoriale identice (zone), fiecare zonă fiind identificată prin tripletul (x,y,c), unde (x,y) reprezintă coordonatele zonei teritoriale (x – linia, y – coloana), iar c cota (înălțimea). Între zonele ocupate de munții există vaste zone de gaz lichid, zone care au cota 0.

Pentru recoltarea și transportul unobtainiumului către baza stelară coloniștii RDA folosesc spice-harvesters, nave speciale cu aterizarea pe verticală.

Aterizarea pe munții plutitori reprezintă o adevărată provocare pentru piloții RDA. Pentru a putea ateriza, piloții trebuie să identifice un sector plat (platformă de aterizare), platformă care să respecte designul trenului de aterizare al navelor (vezi figura alăturată). Platforma are forma unui pătrat de latură k ce este format din k*k zone teritoriale, astfel (k*k)-4 zone au aceeași cotă, iar cele 4 colțuri ale pătratului au cota strict mai mică decât restul zonelor pătratului.

Cerința

Cunoscând descrierea a M zone teritoriale ce alcătuiesc munții plutitori să se determine coordonatele colțului stânga-sus al platformelor de aterizare pentru munții plutitori care permit aterizarea.

Date de intrare

Fișierul de intrare pandora.in conține pe prima linie trei numerele naturale N, k și M, separate prin câte un spațiu, cu semnificația din enunț. Pe următoarele M linii se află descrierea celor M zone ce alcătuiesc munții plutitori, zone date sub forma unui triplet de numere naturale nenule x y c, numerele fiind despărțite prin câte un spațiu.

Date de ieșire

În fișierul de ieșire pandora.out se vor afla scrise, câte o pereche pe linie, coordonatele x, y despărțite prin spațiu, ce reprezintă colțul stânga-sus al platformelor de aterizare pentru fiecare munte plutitor ce permite aterizarea. Dacă nu există platforme de aterizare se va afișa 0.

Restricții și precizări

  • 2 ≤ N ≤ 1000
  • 2 ≤ M ≤ 200000
  • 3 ≤ k < 400
  • 1 ≤ x ≤ N, 1 ≤ y ≤ N
  • 0 ≤ c ≤ 1000
  • Prin munte plutitor înțelegem totalitatea zonelor cu cotă nenulă ce sunt împrejmuite de gaz lichid. și sunt vecine pe una din cele 4 direcții: nord, est, sud, vest. Zona muntoasă este compactă, adică nu conţine în interior zone cu c=0. Munții sunt despărțiți prin zone de gaz. Harta digitală se consideră mărginită de gaz atmosferic.
  • Platformele de aterizare au cote nenule
  • Dacă un munte are mai multe platforme de aterizare se va determina cea cu coordonată x mai mică, iar la coordonate x egale, cea cu coordonata y mai mică.
  • Pentru 10% dintre teste k < 10. Pentru alte 20% dintre teste N ≤ 500.

Exemplu

pandora.in

9 3 43
1 2 1
1 3 2
1 4 1
2 1 4
2 2 2
2 3 2
2 4 2
3 1 3
3 2 1
3 3 2
3 4 1
1 6 2
1 7 3
1 8 1
2 6 3
2 7 3
2 8 3
2 9 1
3 6 1
3 7 3
3 8 2
5 2 1
5 3 4
5 4 3
6 2 4
6 3 4
6 4 4
6 5 4
7 2 2
7 3 4
7 4 3
7 5 3
8 2 2
8 3 2
6 7 5
6 8 2
6 9 5
7 7 2
7 8 2
7 9 2
8 7 1
8 8 2
8 9 1

pandora.out

1 2
5 2
1 6

Explicație

Atenție, platforma din dreapta-jos nu este corectă, deoarece sunt valori din colțuri (valorile de 5) care sunt mai mari decât valorile din platformă.

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 Pandora:

# include <fstream>
# include <queue>
# include <cassert>
using namespace std;

ifstream f("pandora.in");
ofstream g("pandora.out");

const int nM = 1013;
struct zona
{
    short l, c;
}P1, P2;

int dx[] = {0, 1, 0,-1};
int dy[] = {1, 0,-1, 0};

short h[nM][nM];
queue <zona> q;
int Nrmp, Nrs, k, N, M, p;
short l, c;
void fill( short i, short j )
{
    short K;
    h[i][j] = -h[i][j];
    if (i < P1.l) P1.l = i;
    if (j < P1.c) P1.c = j;
    if (i > P2.l) P2.l = i;
    if (j > P2.c) P2.c = j;
    for (K=0; K<4; ++K)
        {
            l = i + dx[K];
            c = j + dy[K];
            if (l > 0 && l <= N && c > 0 && c <= N)
                if (h[l][c] > 0)
                {
                    fill(l, c);
                }
        }
}
bool patrat(short x1, short y1, short x2, short y2)
{
    short i, j;
    int x = h[x1][y1];
    for(i=x1; i<=x2; ++i)
        for(j=y1; j<=y2; ++j)
            if(x != h[i][j]) return 0;
    return 1;
}
bool colturi(short x1, short y1, short x2, short y2)
{
    int x = -h[x1][y1];
    short l1 = x1 - 1, l2 = x2 + 1, c1 = y1 - 1, c2 = y2 + 1;
    short i;
    if (-h[l1][c1] >= x || -h[l1][c2] >= x || -h[l2][c1] >= x || -h[l2][c2] >= x) return 0;
    if (h[l1][c1] == 0 || h[l1][c2] == 0 || h[l2][c1] == 0 || h[l2][c2] == 0) return 0;

    for(i=x1; i<=x2; i++){
        if (-h[i][c1] != x) return 0;
        if (-h[i][c2] != x) return 0;
    }
    for(i=y1; i<=y2; i++){
        if (-h[l1][i] != x) return 0;
        if (-h[l2][i] != x) return 0;
    }
    return 1;
}
bool verif(zona P1, zona P2)
{
    short i, j, l, c;
    int x;
    for(i=P1.l; i<=P2.l; ++i)
        for(j=P1.c; j<=P2.c; ++j)
            if (h[i][j] < 0){
                if (patrat(i, j, i+k-3, j+k-3)){
                    if (colturi(i, j, i+k-3, j+k-3)){
                        g << i-1 << " " << j-1 << "\n";
                        return 1;
                    }
                }
            }
    return 0;
}
int main()
{
    int i, j, x, y, c, ok;

    ///f >> p;
    f >> N >> k >> M;
    p = 2;

    assert(N > 1 && N < 1001);
    assert(k > 1 && k < 400 && k < N);
    assert(M > 1 && M < 200001);

    i = 0;
    while(f >> x >> y >> c)
    {
        assert(x > 0 && x <= N);
        assert(y > 0 && y <= N);
        assert(c > 0 && c <= 1000);
        ++i;
        h[x][y] = c;
    }
    assert(i == M);

    for(i=1; i<=N; ++i)
        for(j=1; j<=N; ++j)
            if (h[i][j] > 0)
            {
                Nrmp++;
                P1.l = P2.l = i;
                P1.c = P2.c = j;
                fill(i, j);
                if (p == 2) ok = verif(P1, P2);
            }

    if (p == 1) g << Nrmp << "\n";

    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 #1714 Pandora

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1714 Pandora 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!