Pieces stand on a board with h rows and w columns.
A cell is . (empty) or one of the letters R, B, Q, N, K, each meaning one piece.
All pieces are enemies of each other, so any piece can attack any other piece.
R attacks a piece in the same row or the same column as itself.
B attacks a piece on the same diagonal as itself, that is, one whose row difference and column difference have the same size.
Q attacks every piece that R would attack and every piece that B would attack.
However, R, B and Q cannot attack a target piece if there is at least one other piece in the cells between itself and the target (the cells on the straight line or diagonal joining the two, excluding the two pieces' own cells). In other words, they cannot attack past another piece.
N attacks a piece that is 1 column and 2 rows away, or 2 columns and 1 row away, and is not blocked by pieces in between.
K attacks a piece in any of the eight cells touching it horizontally, vertically or diagonally.
Given t boards, find for each board the number of pieces that are attacked by no other piece.
The first line gives t. For each board, the first line gives h and w separated by a single space, and the next h lines each give a string of length w.
Print one answer per line for each board. The answer for a board with no pieces is 0.
Input
1 ≤ t ≤ 30. 1 ≤ h, w ≤ 12. A board has from 0 to 40 pieces. The board strings contain only ., R, B, Q, N, K and no spaces
Output
For each board, the number of pieces that are not attacked, one per line
Example 1 · stdin
2
3 4
R..N
.B..
K..Q
1 5
R.N.R
stdout
1
2
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
If you split each 'is it ...?' question into a small function that returns true or false (same line? diagonal? clear between? attacks? safe?), a complicated condition reads as a combination of named questions. The return type is Python bool (True/False), JS/TS boolean, Java boolean, C#/C++ bool, C bool from <stdbool.h>, and Craykon true/false. 'Is there at least one' is Python any(...), JS/TS some, Java streams anyMatch/noneMatch, C# Any, C++ std::any_of/std::none_of; in C and Craykon you return from inside the loop as soon as one is found. Absolute value is abs in Python and C, std::abs in C++, Math.abs in JS/TS/Java, Math.Abs in C#, and Mathf.Abs in Craykon. For the sign there are JS/TS Math.sign, Java Integer.signum and C# Math.Sign, but Python, C, C++ and Craykon have no sign function for integers, so write it yourself. Trap 1: rooks, bishops and queens are blocked by a piece in between; checking only the direction is not enough. Trap 2: returning true right after looking at the first cell inside the loop that checks the gap; return true only after the loop has finished. Trap 3: the cells between exclude both ends (the cells holding the two pieces). Starting from the first piece's own cell makes everything blocked. Trap 4: a diagonal is |row difference| == |column difference|. Without the absolute values you miss the diagonals of one direction. Trap 5: in all eight languages a || b && c groups && (Python and) first, giving a || (b && c). The queen needs parentheses: (straight || diagonal) && clear. Trap 6: writing the knight as 'the two differences add up to 3' also accepts a piece three cells straight away, and writing the king as 'the two differences add up to 1' misses the diagonal neighbours. Trap 7: attacking is not mutual (a rook may attack a knight that cannot attack the rook). Swapping the arguments of attacks(a, b) turns 'someone attacks me' into 'I attack someone'.
Pythonmain.py · 58 lines
import sysdef straight(a, b): """같은 가로줄이나 세로줄에 있는가""" return a[0] == b[0] or a[1] == b[1]def diagonal(a, b): """같은 대각선에 있는가""" return abs(a[0] - b[0]) == abs(a[1] - b[1])def sign(x): return (x > 0) - (x < 0)def clear(board, a, b): """a와 b 사이(양 끝은 빼고)에 말이 하나도 없는가""" dr, dc = sign(b[0] - a[0]), sign(b[1] - a[1]) r, c = a[0] + dr, a[1] + dc while (r, c) != b: if board[r][c] != ".": return False r, c = r + dr, c + dc return Truedef attacks(board, kind, a, b): """a 칸에 있는 kind 말이 b 칸을 공격하는가""" dr, dc = abs(a[0] - b[0]), abs(a[1] - b[1]) if kind == "N": return (dr == 1 and dc == 2) or (dr == 2 and dc == 1) if kind == "K": return max(dr, dc) == 1 if kind == "R": return straight(a, b) and clear(board, a, b) if kind == "B": return diagonal(a, b) and clear(board, a, b) return (straight(a, b) or diagonal(a, b)) and clear(board, a, b)def is_safe(board, pieces, target): """다른 어떤 말도 target을 공격하지 않는가""" return not any(attacks(board, board[p[0]][p[1]], p, target) for p in pieces if p != target)lines = sys.stdin.read().split("\n")t = int(lines[0])at = 1out = []for _ in range(t): h, w = map(int, lines[at].split()) board = [lines[at + 1 + r].strip() for r in range(h)] at += 1 + h pieces = [(r, c) for r in range(h) for c in range(w) if board[r][c] != "."] out.append(sum(1 for p in pieces if is_safe(board, pieces, p)))print("\n".join(map(str, out)))
JavaScriptmain.js · 52 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");// 같은 가로줄이나 세로줄에 있는가const straight = (a, b) => a.r === b.r || a.c === b.c;// 같은 대각선에 있는가const diagonal = (a, b) => Math.abs(a.r - b.r) === Math.abs(a.c - b.c);// a와 b 사이(양 끝은 빼고)에 말이 하나도 없는가function clear(board, a, b) { const dr = Math.sign(b.r - a.r), dc = Math.sign(b.c - a.c); let r = a.r + dr, c = a.c + dc; while (r !== b.r || c !== b.c) { if (board[r][c] !== ".") return false; r += dr; c += dc; } return true;}// a 칸에 있는 말이 b 칸을 공격하는가function attacks(board, a, b) { const dr = Math.abs(a.r - b.r), dc = Math.abs(a.c - b.c); switch (board[a.r][a.c]) { case "N": return (dr === 1 && dc === 2) || (dr === 2 && dc === 1); case "K": return Math.max(dr, dc) === 1; case "R": return straight(a, b) && clear(board, a, b); case "B": return diagonal(a, b) && clear(board, a, b); default: return (straight(a, b) || diagonal(a, b)) && clear(board, a, b); }}// 다른 어떤 말도 target을 공격하지 않는가const isSafe = (board, pieces, target) => !pieces.some((p) => p !== target && attacks(board, p, target));const t = Number(lines[0]);let at = 1;const out = [];for (let k = 0; k < t; k++) { const [h, w] = lines[at].trim().split(" ").map(Number); const board = lines.slice(at + 1, at + 1 + h).map((s) => s.trim()); at += 1 + h; const pieces = []; for (let r = 0; r < h; r++) { for (let c = 0; c < w; c++) { if (board[r][c] !== ".") pieces.push({ r, c }); } } out.push(pieces.filter((p) => isSafe(board, pieces, p)).length);}console.log(out.join("\n"));
TypeScriptmain.ts · 56 lines
import { readFileSync } from "node:fs";type Cell = { r: number; c: number };const lines: string[] = readFileSync(0, "utf8").split("\n");// 같은 가로줄이나 세로줄에 있는가const straight = (a: Cell, b: Cell): boolean => a.r === b.r || a.c === b.c;// 같은 대각선에 있는가const diagonal = (a: Cell, b: Cell): boolean => Math.abs(a.r - b.r) === Math.abs(a.c - b.c);// a와 b 사이(양 끝은 빼고)에 말이 하나도 없는가function clear(board: string[], a: Cell, b: Cell): boolean { const dr = Math.sign(b.r - a.r), dc = Math.sign(b.c - a.c); let r = a.r + dr, c = a.c + dc; while (r !== b.r || c !== b.c) { if (board[r][c] !== ".") return false; r += dr; c += dc; } return true;}// a 칸에 있는 말이 b 칸을 공격하는가function attacks(board: string[], a: Cell, b: Cell): boolean { const dr = Math.abs(a.r - b.r), dc = Math.abs(a.c - b.c); switch (board[a.r][a.c]) { case "N": return (dr === 1 && dc === 2) || (dr === 2 && dc === 1); case "K": return Math.max(dr, dc) === 1; case "R": return straight(a, b) && clear(board, a, b); case "B": return diagonal(a, b) && clear(board, a, b); default: return (straight(a, b) || diagonal(a, b)) && clear(board, a, b); }}// 다른 어떤 말도 target을 공격하지 않는가const isSafe = (board: string[], pieces: Cell[], target: Cell): boolean => !pieces.some((p) => p !== target && attacks(board, p, target));const t = Number(lines[0]);let at = 1;const out: number[] = [];for (let k = 0; k < t; k++) { const [h, w] = lines[at].trim().split(" ").map(Number); const board = lines.slice(at + 1, at + 1 + h).map((s) => s.trim()); at += 1 + h; const pieces: Cell[] = []; for (let r = 0; r < h; r++) { for (let c = 0; c < w; c++) { if (board[r][c] !== ".") pieces.push({ r, c }); } } out.push(pieces.filter((p) => isSafe(board, pieces, p)).length);}console.log(out.join("\n"));
JavaMain.java · 71 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;public class Main { record Cell(int r, int c) {} static String[] board; // 같은 가로줄이나 세로줄에 있는가 static boolean straight(Cell a, Cell b) { return a.r() == b.r() || a.c() == b.c(); } // 같은 대각선에 있는가 static boolean diagonal(Cell a, Cell b) { return Math.abs(a.r() - b.r()) == Math.abs(a.c() - b.c()); } // a와 b 사이(양 끝은 빼고)에 말이 하나도 없는가 static boolean clear(Cell a, Cell b) { int dr = Integer.signum(b.r() - a.r()), dc = Integer.signum(b.c() - a.c()); int r = a.r() + dr, c = a.c() + dc; while (r != b.r() || c != b.c()) { if (board[r].charAt(c) != '.') return false; r += dr; c += dc; } return true; } // a 칸에 있는 말이 b 칸을 공격하는가 static boolean attacks(Cell a, Cell b) { int dr = Math.abs(a.r() - b.r()), dc = Math.abs(a.c() - b.c()); return switch (board[a.r()].charAt(a.c())) { case 'N' -> (dr == 1 && dc == 2) || (dr == 2 && dc == 1); case 'K' -> Math.max(dr, dc) == 1; case 'R' -> straight(a, b) && clear(a, b); case 'B' -> diagonal(a, b) && clear(a, b); default -> (straight(a, b) || diagonal(a, b)) && clear(a, b); }; } // 다른 어떤 말도 target을 공격하지 않는가 static boolean isSafe(List<Cell> pieces, Cell target) { return pieces.stream().noneMatch(p -> !p.equals(target) && attacks(p, target)); } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); for (int k = 0; k < t; k++) { String[] hw = in.readLine().trim().split(" "); int h = Integer.parseInt(hw[0]), w = Integer.parseInt(hw[1]); board = new String[h]; List<Cell> pieces = new ArrayList<>(); for (int r = 0; r < h; r++) { board[r] = in.readLine().trim(); for (int c = 0; c < w; c++) { if (board[r].charAt(c) != '.') pieces.add(new Cell(r, c)); } } long safe = pieces.stream().filter(p -> isSafe(pieces, p)).count(); out.append(safe).append('\n'); } System.out.print(out); }}
C#Main.cs · 70 lines
using System;using System.Collections.Generic;using System.Linq;using System.Text;class Program{ static string[] board; // 같은 가로줄이나 세로줄에 있는가 static bool Straight((int r, int c) a, (int r, int c) b) => a.r == b.r || a.c == b.c; // 같은 대각선에 있는가 static bool Diagonal((int r, int c) a, (int r, int c) b) => Math.Abs(a.r - b.r) == Math.Abs(a.c - b.c); // a와 b 사이(양 끝은 빼고)에 말이 하나도 없는가 static bool Clear((int r, int c) a, (int r, int c) b) { int dr = Math.Sign(b.r - a.r), dc = Math.Sign(b.c - a.c); int r = a.r + dr, c = a.c + dc; while (r != b.r || c != b.c) { if (board[r][c] != '.') return false; r += dr; c += dc; } return true; } // a 칸에 있는 말이 b 칸을 공격하는가 static bool Attacks((int r, int c) a, (int r, int c) b) { int dr = Math.Abs(a.r - b.r), dc = Math.Abs(a.c - b.c); switch (board[a.r][a.c]) { case 'N': return (dr == 1 && dc == 2) || (dr == 2 && dc == 1); case 'K': return Math.Max(dr, dc) == 1; case 'R': return Straight(a, b) && Clear(a, b); case 'B': return Diagonal(a, b) && Clear(a, b); default: return (Straight(a, b) || Diagonal(a, b)) && Clear(a, b); } } // 다른 어떤 말도 target을 공격하지 않는가 static bool IsSafe(List<(int r, int c)> pieces, (int r, int c) target) => !pieces.Any(p => p != target && Attacks(p, target)); static void Main() { int t = int.Parse(Console.ReadLine().Trim()); var output = new StringBuilder(); for (int k = 0; k < t; k++) { int[] hw = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray(); int h = hw[0], w = hw[1]; board = new string[h]; var pieces = new List<(int r, int c)>(); for (int r = 0; r < h; r++) { board[r] = Console.ReadLine().Trim(); for (int c = 0; c < w; c++) { if (board[r][c] != '.') pieces.Add((r, c)); } } output.Append(pieces.Count(p => IsSafe(pieces, p))).Append('\n'); } Console.Write(output); }}
C++main.cpp · 67 lines
#include <algorithm>#include <cstdlib>#include <iostream>#include <string>#include <vector>struct Cell { int r, c; bool operator==(const Cell& o) const { return r == o.r && c == o.c; }};using Board = std::vector<std::string>;// 같은 가로줄이나 세로줄에 있는가bool straight(Cell a, Cell b) { return a.r == b.r || a.c == b.c; }// 같은 대각선에 있는가bool diagonal(Cell a, Cell b) { return std::abs(a.r - b.r) == std::abs(a.c - b.c); }int sign(int x) { return (x > 0) - (x < 0); }// a와 b 사이(양 끝은 빼고)에 말이 하나도 없는가bool clear(const Board& board, Cell a, Cell b) { const int dr = sign(b.r - a.r), dc = sign(b.c - a.c); for (int r = a.r + dr, c = a.c + dc; r != b.r || c != b.c; r += dr, c += dc) { if (board[r][c] != '.') return false; } return true;}// a 칸에 있는 말이 b 칸을 공격하는가bool attacks(const Board& board, Cell a, Cell b) { const int dr = std::abs(a.r - b.r), dc = std::abs(a.c - b.c); switch (board[a.r][a.c]) { case 'N': return (dr == 1 && dc == 2) || (dr == 2 && dc == 1); case 'K': return std::max(dr, dc) == 1; case 'R': return straight(a, b) && clear(board, a, b); case 'B': return diagonal(a, b) && clear(board, a, b); default: return (straight(a, b) || diagonal(a, b)) && clear(board, a, b); }}// 다른 어떤 말도 target을 공격하지 않는가bool isSafe(const Board& board, const std::vector<Cell>& pieces, Cell target) { return std::none_of(pieces.begin(), pieces.end(), [&](Cell p) { return !(p == target) && attacks(board, p, target); });}int main() { int t; std::cin >> t; while (t-- > 0) { int h, w; std::cin >> h >> w; Board board(h); std::vector<Cell> pieces; for (int r = 0; r < h; r++) { std::cin >> board[r]; for (int c = 0; c < w; c++) { if (board[r][c] != '.') pieces.push_back({r, c}); } } std::cout << std::count_if(pieces.begin(), pieces.end(), [&](Cell p) { return isSafe(board, pieces, p); }) << '\n'; }}
Cmain.c · 65 lines
#include <stdbool.h>#include <stdio.h>#include <stdlib.h>typedef struct { int r, c; } Cell;static char board[12][13];/* 같은 가로줄이나 세로줄에 있는가 */static bool straight(Cell a, Cell b) { return a.r == b.r || a.c == b.c; }/* 같은 대각선에 있는가 */static bool diagonal(Cell a, Cell b) { return abs(a.r - b.r) == abs(a.c - b.c); }static int sign(int x) { return (x > 0) - (x < 0); }/* a와 b 사이(양 끝은 빼고)에 말이 하나도 없는가 */static bool clear(Cell a, Cell b) { int dr = sign(b.r - a.r), dc = sign(b.c - a.c); for (int r = a.r + dr, c = a.c + dc; r != b.r || c != b.c; r += dr, c += dc) { if (board[r][c] != '.') return false; } return true;}/* a 칸에 있는 말이 b 칸을 공격하는가 */static bool attacks(Cell a, Cell b) { int dr = abs(a.r - b.r), dc = abs(a.c - b.c); switch (board[a.r][a.c]) { case 'N': return (dr == 1 && dc == 2) || (dr == 2 && dc == 1); case 'K': return (dr > dc ? dr : dc) == 1; case 'R': return straight(a, b) && clear(a, b); case 'B': return diagonal(a, b) && clear(a, b); default: return (straight(a, b) || diagonal(a, b)) && clear(a, b); }}/* 다른 어떤 말도 pieces[target]을 공격하지 않는가 */static bool is_safe(const Cell *pieces, int count, int target) { for (int i = 0; i < count; i++) { if (i != target && attacks(pieces[i], pieces[target])) return false; } return true;}int main(void) { int t; scanf("%d", &t); while (t-- > 0) { int h, w, count = 0, safe = 0; Cell pieces[40]; scanf("%d %d", &h, &w); for (int r = 0; r < h; r++) { scanf("%12s", board[r]); for (int c = 0; c < w; c++) { if (board[r][c] != '.') pieces[count++] = (Cell){r, c}; } } for (int i = 0; i < count; i++) { if (is_safe(pieces, count, i)) safe++; } printf("%d\n", safe); } return 0;}
Craykonmain.cray · 111 lines
판 = [];// 말이 있는 칸의 줄 번호와 칸 번호줄들 = [];칸들 = [];부호(x){ if (x > 0) { return 1; } if (x < 0) { return -1; } return 0;}// 같은 가로줄이나 세로줄에 있는가곧은줄인가(a, b){ return 줄들[a] == 줄들[b] || 칸들[a] == 칸들[b];}// 같은 대각선에 있는가대각선인가(a, b){ return Mathf.Abs(줄들[a] - 줄들[b]) == Mathf.Abs(칸들[a] - 칸들[b]);}// a와 b 사이(양 끝은 빼고)에 말이 하나도 없는가비었나(a, b){ dr = 부호(줄들[b] - 줄들[a]); dc = 부호(칸들[b] - 칸들[a]); r = 줄들[a] + dr; c = 칸들[a] + dc; while (r != 줄들[b] || c != 칸들[b]) { if (판[r][c] != ".") { return false; } r += dr; c += dc; } return true;}// a번 말이 b번 말을 공격하는가공격하나(a, b){ dr = Mathf.Abs(줄들[a] - 줄들[b]); dc = Mathf.Abs(칸들[a] - 칸들[b]); switch (판[줄들[a]][칸들[a]]) { case "N": return dr == 1 && dc == 2 || dr == 2 && dc == 1; case "K": return Mathf.Max(dr, dc) == 1; case "R": return 곧은줄인가(a, b) && 비었나(a, b); case "B": return 대각선인가(a, b) && 비었나(a, b); } return (곧은줄인가(a, b) || 대각선인가(a, b)) && 비었나(a, b);}// 다른 어떤 말도 b번 말을 공격하지 않는가안전한가(b){ for (i = 0; i < 줄들.Count; i++) { if (i != b && 공격하나(i, b)) { return false; } } return true;}t = Console.ReadLine().ToNumber();for (k = 0; k < t; k++){ hw = Console.ReadNumbers(); 판 = []; 줄들 = []; 칸들 = []; for (r = 0; r < hw[0]; r++) { 줄 = Console.ReadLine().Trim(); 판.Add(줄); for (c = 0; c < hw[1]; c++) { if (줄[c] != ".") { 줄들.Add(r); 칸들.Add(c); } } } 안전 = 0; for (i = 0; i < 줄들.Count; i++) { if (안전한가(i)) { 안전++; } } Console.WriteLine(안전);}