Cerința

Se consideră o tablă de șah de dimensiune n (alcătuită din n linii si n coloane), pe care se află m piese de șah, fiecare putând fi: pion, rege, regină, nebun, tură sau cal). Se dau coordonatele a t căsuțe de pe tablă și se cere să se verifice pentru fiecare dacă este atacată, ocupată sau neatacată de piesele care se află pe tablă .

Date de intrare

Fișierul de intrare piesesah.in conține pe prima linie trei numere n m t. Următoarele m linii conțin un caracter, literă mică (reprezentând tipul piesei) urmat de două numere naturale reprezentând coordonatele piesei. Următoarele t linii conțin câte două numere naturale reprezentând coordonatele unei căsuțe care trebuie verificată.

Date de ieșire

Fișierul de ieșire piesesah.out va conține pe t linii câte un singur număr natural 0 , 1 sau 2, după cum căsuța corespunzătoare este neatacată, atacată sau ocupată.

Restricții și precizări

• 1 ≤ n ≤ 1000
• 1 ≤ m < n * n
• 1 ≤ t ≤ 50000
• Nu vor exista două piese pe aceeași poziție;
• Caracterele care precizează piesele de pe tablă pot fi:
  • p – pion;
  • r – rege;
  • q – regină;
  • n – nebun;
  • t – tură;
  • c – cal;
• Piesele de pe tablă atacă astfel:
  • regele atacă oricare dintre cele 8 căsuțe vecine pe linie, coloană sau diagonale, situate pe tablă;
  • pionul atacă oricare dintre cele 4 căsuțe vecine pe diagonale, situate pe tablă;
  • calul atacă oricare dintre 8 căsuțe, situate pe tablă, în care poate ajunge sărind în L;
  • regina atacă orice căsuță de pe tablă aflată pe aceeași linie, coloană sau diagonală cu ea, dar până la întâlnirea altei piese;
  • nebunul atacă orice căsuță de pe tablă aflată pe aceeași diagonală cu el, dar până la întâlnirea altei piese;
  • tura atacă orice căsuță de pe tablă aflată pe aceeași linie sau coloană cu ea, dar până la întâlnirea altei piese;

Exemplul 1

piesesah.in

10 6 10
p 1 1
r 8 9
q 3 2
n 6 7
t 2 9
c 9 3
1 1
5 5
2 3
5 2
9 6
8 9
10 10
9 2
2 2
7 2

piesesah.out

2
0
1
1
0
2
0
1
1
1

Explicație

Tabla de șah arată astfel:

2 1 0 1 0 0 0 0 1 0 
1 1 1 1 1 1 1 1 2 1 
1 2 1 1 1 1 1 1 1 1 
1 1 1 0 1 0 0 0 1 0 
0 1 0 1 0 1 0 1 1 0 
0 1 0 0 1 0 2 0 1 0 
0 1 0 1 0 1 0 1 1 1 
1 1 0 0 1 0 1 1 2 1 
0 1 2 1 0 0 0 1 1 1 
1 1 1 0 1 0 0 0 1 0

Exemplul 2

piesesah.in

7 4 5
q 5 5
p 3 3
c 5 2
r 7 7
4 4
5 1
1 1
7 3
3 3

piesesah.out

1
0
0
1
2

Explicație

Tabla de șah arată astfel:

0 0 0 0 1 0 0 
0 1 0 1 1 0 0 
1 0 2 0 1 0 1 
0 1 0 1 1 1 0 
0 2 1 1 2 1 1 
0 0 0 1 1 1 1 
1 0 1 0 1 1 2 

#include <bits/stdc++.h>
using namespace std;

ifstream cin("piesesah.in");
ofstream cout("piesesah.out");

const int dit[] = {-1 , 0 , 1 ,  0};///tura
const int djt[] = { 0 , 1 , 0 , -1};
const int dip[] = {-1 , -1 , 1 ,  1};///pion si nebun
const int djp[] = { 1 , -1 , 1 , -1};
const int dir[] = {-1 , -1 , -1 ,  0 , 0 ,  1 , 1 , 1};///rege si regina
const int djr[] = {-1 ,  0 ,  1 , -1 , 1 , -1 , 0 , 1};
const int dic[] = {-2 , -2 , -1 , 1 , 2 ,  2 ,  1 , -1};///cal
const int djc[] = {-1 ,  1 ,  2 , 2 , 1 , -1 , -2 , -2};

struct piese
{
    char t;
    int i , j;
};
int a[1001][1001] , n;
piese p[1000001];

int inside(int i , int j)
{
    return i >= 1 && i <= n  && j >= 1 && j <= n;
}

void tura(int x , int y)
{
    for(int k = 0 ; k < 4 ; k++)
    {
        int i = x + dit[k];
        int j = y + djt[k];
        while(inside(i , j) && a[i][j] != 2)
        {
            a[i][j] = 1;
            i += dit[k];
            j += djt[k];
        }
    }
}

void nebun(int x , int y)
{
    for(int k = 0 ; k < 4 ; k++)
    {
        int i = x + dip[k];
        int j = y + djp[k];
        while(inside(i , j) && a[i][j] != 2)
        {
            a[i][j] = 1;
            i += dip[k];
            j += djp[k];
        }
    }
}

void regina(int x , int y)
{
    for(int k = 0 ; k < 8 ; k++)
    {
        int i = x + dir[k];
        int j = y + djr[k];
        while(inside(i , j) && a[i][j] != 2)
        {
            a[i][j] = 1;
            i += dir[k];
            j += djr[k];
        }
    }
}

void rege(int x , int y)
{
    for(int k = 0 ; k < 8 ; k++)
    {
        int i = x + dir[k];
        int j = y + djr[k];
        if(inside(i , j) && a[i][j] == 0) a[i][j] = 1;
    }
}

void cal(int x , int y)
{
    for(int k = 0 ; k < 8 ; k++)
    {
        int i = x + dic[k];
        int j = y + djc[k];
        if(inside(i , j) && a[i][j] == 0) a[i][j] = 1;
    }
}

void pion(int x , int y)
{
    for(int k = 0 ; k < 4 ; k++)
    {
        int i = x + dip[k];
        int j = y + djp[k];
        if(inside(i , j) && a[i][j] == 0) a[i][j] = 1;
    }
}
int main()
{
    int m , t , x , y;
    cin >> n >> m >> t;
    for(int i = 1 ; i <= m ; i++)
    {
        cin >> p[i].t >> p[i].i >> p[i].j;
        a[p[i].i][p[i].j] = 2;
    }
    for(int i = 1 ; i <= m ; i++)
    {
        if(p[i].t == 'n') nebun(p[i].i , p[i].j);
        if(p[i].t == 't') tura(p[i].i , p[i].j);
        if(p[i].t == 'q') regina(p[i].i , p[i].j);
        if(p[i].t == 'c') cal(p[i].i , p[i].j);
        if(p[i].t == 'p') pion(p[i].i , p[i].j);
        if(p[i].t == 'r') rege(p[i].i , p[i].j);
    }
    for(int i = 1 ; i <= t ; i++)
    {
        cin >> x >> y;
        cout << a[x][y] << '\n';
    }
}