# PBinfo #602 – Regine – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: andrei

## Enunț

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

8 9
1 7
2 2 
2 8
4 1
5 2
5 5
5 8
7 2
7 7
regine.out

5 1
Explicație

## Cod sursă C++

```cpp
//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;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/602)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/602/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-602/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)