Cerința

Pe o tablă de șah de dimensiune n se află m regine. O regină atacă o altă regină dacă cele două se află pe aceeași linie, coloană sau diagonală și între ele nu se află alte regine. Determinați numărul maxim p de regine care sunt atacate de o aceeași regină și numărul q de regine care atacă p alte regine.

Date de intrare

Fișierul de intrare regine.in conține pe prima linie numerele n m; următoarele m linii conțin perechi i j reprezentând linia și coloana unde se află poziționată o regină.

Date de ieșire

Fișierul de ieșire regine.out va conține pe prima linie numerele p q, separate prin exact un spațiu, reprezentând valorile de mai sus.

Restricții și precizări

1 ≤ n ≤ 100
1 ≤ m ≤ 500
1 ≤ i,j ≤ n
pe tablă nu există două regine suprapuse

Exemplu

regine.in

regine.out

5 1

Explicație

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

//regine

#include <iostream>
#include <fstream>
using namespace std;

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

const int di[]={-1,-1,-1, 0, 0, 1, 1, 1},
          dj[]={-1, 0, 1,-1, 1,-1, 0, 1};

int a[105][105], n, m ;

int main(){
    fin  >> n >> m ;
    for(int k = 1 ; k <= m ; ++k)
    {
        int i ,j ;
        fin >> i >> j;
        a[i][j] = 1;
        
    }
    int  p = 0 , q = 0;
    for(int i =1 ; i <= n ; ++i)
        for(int j =1 ; j <= n ; ++j)
            if(a[i][j] == 1)
            {
                int cnt = 0;
                for(int k = 0 ; k < 8 ; k ++)
                {
                    int x = 1;
                    while(i + di[k] * x > 0 && i + di[k] * x <= n && j + dj[k] * x > 0 && j + dj[k] * x <= n && a[i + di[k] * x][j + dj[k] * x] == 0)
                        x ++;
                    if(a[i + di[k] * x][j + dj[k] * x] == 1)
                        cnt ++;
                }
                if(cnt > p)
                    p = cnt, q = 1;
                else
                    if(cnt == p)
                        q ++;
            }
    fout << p << " " << q << endl;
    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 #602 Regine

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

Rezolvare completă PbInfo #602 Regine