ACHESS - Adventurous Chess Masters

no tags 

The world of the Adventurous Chess Masters is quite different than our world, instead of having streets and buildings everything is composed of a big chess board and chess pieces. A square of a chess board is said to be covered if at least one chess piece is placed on it. The mysteries of the world can be revealed by covering special magical squares over the chess board, and you can't wait to discover them.

In every turn you can update the board by moving one of the pieces on the board according to the following rules:

  • The king moves only one square in any direction.
  • The queen moves any number of squares in any direction along a row, column, or diagonal.
  • The rook moves any number of squares along rows or columns (forward, backward, left or right).
  • The bishop moves any number of squares diagonally.
  • The knight moves to a square in an "L"-shape (two spaces forward, backward, left, or right and one space perpendicular to it).
  • The pawn can only move one space forward or backward (unlike a chess game).

Note that, unlike normal chess, more than one piece can occupy the same square and pieces can move through occupied squares. To reveal the secrets of the world you have to make the maximum number of magical squares covered, in the minimum number of turns.

Input Specification:

The first line of input contains an integer T that represents the number of test cases, then follow T test cases. The first line of each test case contains P and L, the number of chess pieces on the board and the number of magical squares in order.  Following the first line P lines each contains two integers x and y coordinates of the location of the piece where (1 ≤ x, y ≤ 8) and the type of the chess pieces (king, queen, rook, bishop, knight, or pawn…all in small letters) and the last L lines of the test case each contains a unique pair of integers x and y as the coordinates of the magical squares where (1 ≤ x, y ≤ 8). Note that: (0 ≤ P ≤ 64), and these P pieces won't be in any of the L given locations.

Output Specification:

For each test case, print on one line “Case K: Secret reveals after moving H pieces with minimum number of moves M.” Where K is test case number, H is the number of pieces to be moved and M is the total number of moves used. Check Sample below to see the format.

Sample input:

2
1 1
1 1 pawn
8 1
3 5
2 8 king
2 8 queen
7 5 bishop
1 1
2 2
3 6
6 3
4 4

Sample Output:

Case 1: Secret reveals after moving 1 pieces with minimum number of moves 7.
Case 2: Secret reveals after moving 3 pieces with minimum number of moves 5.


hide comments
[Rampage] Blue.Mary: 2011-11-15 15:44:37

You're right. The problem statement should be updated.

Miguel Oliveira: 2011-11-15 15:44:37

XilinX, I interpreted the problem statement as you and had WA. I finally got it AC, the answer to your input is

Case 1: Secret reveals after moving 2 pieces with minimum number of moves 2.
Case 2: Secret reveals after moving 2 pieces with minimum number of moves 5.

Which means that you don't need to check if a piece is actually moved, just the number of magical squares you can cover.

Miguel Oliveira: 2011-11-15 15:44:37

it didn't trigger an assert(P < 300). I also think the author should have provided it.
I have WA though. Not sure if my code ran all the test cases

Also, is "P" in the output the same "P" in the input or the output is the number of pieces that we actually need to move? I think the latter makes more sense (but using the same letter is weird). I tried both ways and both gave maintained the WA

I think the sample is too simple :/

Last edit: 2011-11-14 14:48:38
[Rampage] Blue.Mary: 2011-11-15 15:44:37

What's the answer for this test case:

2
2 2
1 1 bishop
2 2 bishop
2 2
3 1
2 2
1 1 knight
3 3 queen
3 3
8 8

Currently my program outputs:
Case 1: Secret reveals after moving 1 pieces with minimum number of moves 2.
Case 2: Secret reveals after moving 2 pieces with minimum number of moves 5.

Last edit: 2011-11-15 12:40:24

Added by:Mostafa Saad Ibrahim
Date:2011-11-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:10th Egyptian Collegiate Programming Contest