Problem D: Queens, Knights and Pawns
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=88443#problem/D
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.) Q P Q K 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 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 00 0 0
Sample Output
Board 1 has 6 safe squares. Board 2 has 0 safe squares. Board 3 has 996998 safe squares.
HINT
题意
给你一个棋盘，棋盘上面有士兵，有皇后，有马
士兵不会动，皇后攻击范围是八个方向的直线，马是日字
然后问你最后有多少个格子是安全的
题解：
直接暴力就好了
代码：
//qscqesze #include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <queue> #include <typeinfo> #include <fstream> #include <map> #include <stack> typedef long long ll; using namespace std; //freopen("D.in","r",stdin); //freopen("D.out","w",stdout); #define sspeed ios_base::sync_with_stdio(0);cin.tie(0) #define maxn 200051 #define mod 10007 #define eps 1e-9 int Num; //const int inf=0x7fffffff; //нчоч╢С const int inf=0x3f3f3f3f; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } //************************************************************************************** int n,m; int s[1200][1200]; //queens, knights and pawns int ans=0; void check(int x,int y) { if(x<1||x>n||y<1||y>m) return; if(s[x][y]==0) { s[x][y]=1; ans++; } } void at_queue(int x,int y) { check(x,y); for(int i=x;i<=n;i++) { if(s[i][y]==2) break; check(i,y); } for(int i=x;i>=1;i--) { if(s[i][y]==2) break; check(i,y); } for(int i=y;i>=1;i--) { if(s[x][i]==2) break; check(x,i); } for(int i=y;i<=m;i++) { if(s[x][i]==2) break; check(x,i); } for(int i=x,j=y;i<=n&&j<=m;i++,j++) { if(s[i][j]==2) break; check(i,j); } for(int i=x,j=y;i>=1&&j>=1;j--,i--) { if(s[i][j]==2) break; check(i,j); } for(int i=x,j=y;i>=1&&j<=m;i--,j++) { if(s[i][j]==2) break; check(i,j); } for(int i=x,j=y;i<=n&&j>=1;i++,j--) { if(s[i][j]==2) break; check(i,j); } } void at_knight(int x,int y) { check(x,y); check(x+1,y+2); check(x+2,y+1); check(x-1,y+2); check(x-2,y+1); check(x+1,y-2); check(x+2,y-1); check(x-1,y-2); check(x-2,y-1); } struct node { int x,y; }; node que[120]; node kni[120]; int main() { int t=1; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==0) break; ans=0; memset(que,0,sizeof(que)); memset(kni,0,sizeof(kni)); memset(s,0,sizeof(s)); int k1=read(); for(int i=0;i<k1;i++) { que[i].x=read(); que[i].y=read(); } int k2=read(); for(int i=0;i<k2;i++) { kni[i].x=read(); kni[i].y=read(); int x=kni[i].x,y=kni[i].y; if(s[x][y]==0) { s[x][y]=2; ans++; } } int k3=read(); for(int i=0;i<k3;i++) { int x=read(); int y=read(); if(s[x][y]==0) { s[x][y]=2; ans++; } } for(int i=0;i<k1;i++) at_queue(que[i].x,que[i].y); for(int i=0;i<k2;i++) at_knight(kni[i].x,kni[i].y); printf("Board %d has %d safe squares. ",t++,n*m-ans); } }