1221 - PieseSah

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;

Exemplu

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

def attack_positions_pawn(x, y, color, n):
    attacks = []
    if color == 'white':
        if x > 0 and y > 0:
            attacks.append((x - 1, y - 1))
        if x > 0 and y < n - 1:
            attacks.append((x - 1, y + 1))
    else:  # black
        if x < n - 1 and y > 0:
            attacks.append((x + 1, y - 1))
        if x < n - 1 and y < n - 1:
            attacks.append((x + 1, y + 1))
    return attacks

def attack_positions_king(x, y, n):
    attacks = []
    for dx in range(-1, 2):
        for dy in range(-1, 2):
            if dx == 0 and dy == 0:
                continue
            if 0 <= x + dx < n and 0 <= y + dy < n:
                attacks.append((x + dx, y + dy))
    return attacks

def attack_positions_knight(x, y, n):
    moves = [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)]
    attacks = []
    for dx, dy in moves:
        if 0 <= x + dx < n and 0 <= y + dy < n:
            attacks.append((x + dx, y + dy))
    return attacks

def attack_positions_bishop(x, y, n):
    attacks = []
    for i in range(1, n):
        if 0 <= x + i < n and 0 <= y + i < n:
            attacks.append((x + i, y + i))
        if 0 <= x - i < n and 0 <= y + i < n:
            attacks.append((x - i, y + i))
        if 0 <= x + i < n and 0 <= y - i < n:
            attacks.append((x + i, y - i))
        if 0 <= x - i < n and 0 <= y - i < n:
            attacks.append((x - i, y - i))
    return attacks

def attack_positions_rook(x, y, n):
    attacks = []
    for i in range(1, n):
        if 0 <= x + i < n:
            attacks.append((x + i, y))
        if 0 <= x - i < n:
            attacks.append((x - i, y))
        if 0 <= y + i < n:
            attacks.append((x, y + i))
        if 0 <= y - i < n:
            attacks.append((x, y - i))
    return attacks

def attack_positions_queen(x, y, n):
    return attack_positions_bishop(x, y, n) + attack_positions_rook(x, y, n)

def is_attacked(board, x, y):
    return board[x][y] == 1

def main():
    # Citirea dimensiunii tablei de șah
    n = int(input().strip())
    
    # Citirea numărului de piese
    m = int(input().strip())
    
    # Inițializarea tablei de șah
    board = [[0] * n for _ in range(n)]
    
    # Citirea pieselor și plasarea lor pe tabla de șah
    for _ in range(m):
        piece_info = input().strip().split()
        piece_type = piece_info[0]
        x = int(piece_info[1]) - 1  # Transformare la index 0
        y = int(piece_info[2]) - 1  # Transformare la index 0
        color = piece_info[3] if len(piece_info) > 3 else None  # doar pentru pion
        
        # Marcare poziție ocupată
        board[x][y] = 2
        
        # Obținerea pozițiilor atacate
        if piece_type == "pion":
            attacks = attack_positions_pawn(x, y, color, n)
        elif piece_type == "rege":
            attacks = attack_positions_king(x, y, n)
        elif piece_type == "regina":
            attacks = attack_positions_queen(x, y, n)
        elif piece_type == "nebun":
            attacks = attack_positions_bishop(x, y, n)
        elif piece_type == "tura":
            attacks = attack_positions_rook(x, y, n)
        elif piece_type == "cal":
            attacks = attack_positions_knight(x, y, n)
        
        # Marcare poziții atacate
        for ax, ay in attacks:
            board[ax][ay] = max(board[ax][ay], 1)
    
    # Citirea coordonatelor ce trebuiesc verificate
    t = int(input().strip())
    for _ in range(t):
        x, y = map(int, input().strip().split())
        x -= 1  # Transformare la index 0
        y -= 1  # Transformare la index 0
        
        if board[x][y] == 2:
            print("ocupata")
        elif board[x][y] == 1:
            print("atacata")
        else:
            print("neatacata")

if __name__ == "__main__":
    main()