QKP - Queens, Knights and Pawns

no tags 

You all are familiar with the famous 8-queens problem which asks you to place 8 queens on a chess board so no two attack each other. In this problem, you will be given locations of queens and knights and pawns and asked to find how many of the unoccupied squares on the board are not under attack from either a queen or a knight (or both). We’ll call such squares “safe” squares. Here, pawns will only serve as blockers and have no capturing ability. The board below has 6 safe squares. (The shaded squares are safe.)

subir imagenes

Recall that a knight moves to any unoccupied square that is on the opposite corner of a 2x3 rectangle from its current position; a queen moves to any square that is visible in any of the eight horizontal, vertical, and diagonal directions from the current position. Note that the movement of a queen can be blocked by another piece, while a knight’s movement can not.

Input

There will be multiple test cases. Each test case will consist of 4 lines. The first line will contain two integers n and m, indicating the dimensions of the board, giving rows and columns, respectively. Neither integer will exceed 1000. The next three lines will each be of the form

k r1 c1 r2 c2 · · · rk ck

indicating the location of the queens, knights and pawns, respectively. The numbering of the rows and columns will start at one. There will be no more than 100 of any one piece. Values of n = m = 0 indicate end of input.

Output

Each test case should generate one line of the form

Board b has s safe squares.

where b is the number of the board (starting at one) and you supply the correct value for s.

Example

4 4
2 1 4 2 4
1 1 2
1 2 3
2 3
1 1 2
1 1 1
0
1000 1000
1 3 3
0
0
0 0

Output:
Board 1 has 6 safe squares.
Board 2 has 0 safe squares.
Board 3 has 996998 safe squares.

hide comments
luugiam: 2019-09-22 06:14:35

if you can't AC try test case:
10 10
2 2 2 5 5
0
0
output is 48 is true.

tungtd95: 2016-08-10 20:23:56

plzzz give me some test case, getting Runtime Error when summit but it's fine on my laptop with test case Example

thuong_nguyen: 2016-08-10 03:18:20

I AC! Please Note Clause!

tranchiendinh: 2016-03-08 17:04:23

My program pass all my test case. but when I submit, it notify "wrong answer ". Can you help me.
Contact to me: dinhchien94@gmail.com or Skype: dinhtranchien.
Other: give me email or skype, I'll contact to you.
Thanks you so much.

Shail Shah: 2014-09-12 13:32:07

Very interesting problem.
AC in first go :)
Find some pattern hierarchy

Why less people on this problem? :(


Come on guys, increase ur leaderboard asap

Ashok: 2012-11-01 04:42:35

nice problem :)
wonder why only 383 have solved it..

nitish_goyal28: 2011-07-24 17:08:17

some hard test case please...

islam: 2010-01-22 02:18:09

it is weird that the same code some time AC some time TLE
plz increase teh TL as the right algorithm don't pass in slow languages

abhijith reddy d: 2009-09-10 11:50:51

Nice Problem :)


Added by:Camilo Andrés Varela León
Date:2007-07-26
Time limit:0.400s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:East Central North America 2005