Description

Translated from [CERC2018] The Lord of the Kings.

After many years of war with overseas countries, our nation has finally managed to remove most rebels and enemies. Such a glorious victory should be remembered and celebrated for a long time. Therefore, our King declared the Victory Day a public holiday and decided to hold a victory parade. In the parade, the army will follow the King from his palace and visit every city in the country.

The King and his entourage will use an eco-friendly electric helicopter as transportation. This helicopter has a drawback: its range is short. The King asks you and your advisors to build helipads in some farms and in cities, so that starting from his palace, after stopping at some helipads, it is possible to reach any city. However, building helipads and the required infrastructure is expensive, so you need to minimize the number of helipads to build.

In addition, due to the helicopter’s special design, the King and his soldiers must move in a special way, which affects the number and locations of helipads.

You are given a rectangular grid map of the country, containing cells that represent villages, cities, and the palace. You are also given the helicopter’s movement rule, which is the same as one of the chess pieces: Rook, Queen, Bishop, Knight, or King (the detailed movement rules for each piece are shown in “Constraints and Hint”). Your task is to compute the minimum number of helipads that need to be built on farms or cities to satisfy the King’s requirements. There is already a helipad at the King’s palace, so you do not need to build a new one there.

Input Format

The first line contains two integers $N, M$, meaning the country has $N$ rows and $M$ columns.

The second line contains two integers $X, Y$, meaning the location of the King’s palace, followed by a character indicating the movement rule (R for Rook, Q for Queen, B for Bishop, N for Knight, K for King).

The third line contains an integer $T$, meaning the number of cities in the country.

The next $T$ lines each contain two integers $W, Z$, meaning the location of a city. All cities are in different cells, and no city shares the same cell with the palace. All cells that are neither a city nor the palace are farms.

Output Format

Output one integer on a single line, meaning the minimum number of helipads that must be built. If it is impossible for the King and his soldiers to reach every city, output $-1$.

3 3
3 1 K
2
1 1
1 3

3

3 3
3 1 Q
2
1 1
1 3

2

5 5
4 4 R
4
1 2
2 1
2 5
5 1

6

Hint

$1 \le N, M \le 15, 1 \le T \le 10, 1 \le X, W \le N, 1 \le Y, Z \le M$.

The figure below shows the helicopter’s movement rules (the same as the corresponding chess piece’s legal moves).

Translated by ChatGPT 5