Constraints

Time Limit: 1 secs, Memory Limit: 64 MB

Description 

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.) 

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.

Sample Input

4 42 1 4 2 41 1 21 2 32 31 1 21 1 101000 10001 3 3000 0

Sample Output

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


分析：没想到什么好方法，针对每个Queen、Knight来找出能够被他们occupied的点。
　　　能够被Queen occupied 的点都在以当前Queen的坐标为中心，向八个方向射线上的点。

      可以构建两个方向数组change_x[8] = {-1, -1, -1, 0, 1, 1, 1, 0},  change_y[8] = {1, 0, -1, -1, -1, 0, 1, 1}，以Queen为中心向八个方向辐射，直到被Knight或者Pawn阻挡。
　　　
      Knight类似于中国象棋中的“马”，可以走“日”字路。
　　　 
      同样构建两个方向数组change_x[8] = {-1, -2, -2, -1, 1, 2, 2, 1},  change_y[8] = {2, 1, -1, -2, -2, -1, 1, 2}，寻找Knight周围的八个点。

#include <iostream>#include <memory.h>using namespace std;struct role{	int x;	int y;};role queens[100];role knights[100];role pawns[100];char board[1000][1000];void occupiedByQueens(int row, int col, int q_num){	int i, j, x, y, current_x, current_y;	int change_x[8] = {-1, -1, -1, 0, 1, 1, 1, 0};	int change_y[8] = {1, 0, -1, -1, -1, 0, 1, 1};	for(i = 0; i < q_num; i++){		current_x = queens[i].x;		current_y = queens[i].y;		for(j = 0; j < 8; j++){			x = current_x + change_x[j];			y = current_y + change_y[j];			while(x >= 0 && x < row && y >= 0 && y < col){				if(board[x][y] != ‘Q‘ && board[x][y] != ‘K‘ && board[x][y] != ‘P‘){					board[x][y] = ‘O‘;           //‘O‘ for be occupied.				} else {					break;				}				x = x + change_x[j];				y = y + change_y[j];			}		}	}}void occupiedByKnights(int row, int col, int k_num){	int i, j, x, y, current_x, current_y;	int change_x[8] = {-1, -2, -2, -1, 1, 2, 2, 1};	int change_y[8] = {2, 1, -1, -2, -2, -1, 1, 2};	for(i = 0; i < k_num; i++){		current_x = knights[i].x;		current_y = knights[i].y;		for(j = 0; j < 8; j++){			x = current_x + change_x[j];			y = current_y + change_y[j];			if(x >= 0 && x < row && y >= 0 && y < col && board[x][y] == ‘S‘){				board[x][y] = ‘O‘;               //‘O‘ for be occupied.			}		}	}}int main(){	int n, m, i, j, t, x, y, sum, counter = 0;	int q_num, k_num, p_num;	while(cin >> n >> m && n != 0 && m != 0){		memset(board, ‘S‘, sizeof(board));       //‘S‘ for safe.		cin >> q_num;		for(i = 0; i < q_num; i++){			cin >> x >> y;			queens[i].x = x - 1;			queens[i].y = y - 1;			board[x-1][y-1] = ‘Q‘;               //‘Q‘ for occupied by Queen.		}		cin >> k_num;		for(i = 0; i < k_num; i++){			cin >> x >> y;			knights[i].x = x - 1;			knights[i].y = y - 1;			board[x-1][y-1] = ‘K‘;               //‘K‘ for occupied by Knight.		}		cin >> p_num;		for(i = 0; i < p_num; i++){			cin >> x >> y;			pawns[i].x = x - 1;			pawns[i].y = y - 1;			board[x-1][y-1] = ‘P‘;               //‘P‘ for occupied by Pawn.		}		occupiedByQueens(n, m, q_num);		occupiedByKnights(n, m, k_num);		sum = 0;		for(i = 0; i < n; i++){			for(j = 0; j < m; j++){				if(board[i][j] == ‘S‘){					sum++;				}			}		}		cout << "Board " << ++counter << " has " << sum << " safe squares." << endl;	}	return 0;}

Sicily 1172. Queens, Knights and Pawns