洛谷P2105 K皇后

To 洛谷.2105 K皇后

题目描述

小Z最近捡到了一个棋盘，他想在棋盘上摆放K个皇后。他想知道在他摆完这K个皇后之后，棋盘上还有多少了格子是不会被攻击到的。

（Ps：一个皇后会攻击到这个皇后所在的那一行，那一列，以及两条对角线）

输入输出格式

输入格式：

第一行三个正整数 n，m，K，表示棋盘的行列，以及小Z摆放了K个皇后。

接下来K行，每行两个正整数x，y，表示这个皇后被摆在了第x行，第y列，数据保证没有任何两个皇后会被摆在同一个格子里。

输出格式：

一行一个整数，表示棋盘上还有多少了格子是不会被攻击到的。

输入输出样例

输入样例#1：

输出样例#1：

说明

【数据规模和约定】

对于 30%的数据，1 ≤ n，m ≤ 5000，1 ≤ k ≤ 500。

对于另外 10%的数据，k =1。

对于 100%的数据，1 ≤ n，m ≤ 20000，1 ≤ k ≤ 500。

【时空限制】

1s/16M

代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 const int N=20005;
 5 const int K=505;
 6 
 7 int n,m,k,Ans,X[K],Y[K];
 8 bool vis[N];
 9 
10 void read(int &now)
11 {
12     now=0;char c=getchar();
13     while(c>'9'||c<'0')c=getchar();
14     while(c>='0'&&c<='9')now=(now<<3)+(now<<1)+c-'0',c=getchar();
15 }
16 
17 int main()
18 {
19     read(n);read(m);read(k);
20     for(int i=1;i<=k;++i)
21       read(X[i]),read(Y[i]);
22     for(int i=1;i<=n;++i)
23     {
24         int tmp=m;
25         for(int j=1;j<=k;++j)
26         {//枚举m列(20000)会超时，那就枚举k个棋子(500) 
27             if(X[j]==i)
28             {//棋子j能吃到整一行，这一行不被攻击的棋子为0，退出循环 
29                 tmp=0;break;
30             }
31 //            int t1,t2;
32 //            if(X[j]<Y[j])
33 //              t1=Y[j],t2=X[j];
34 //            else
35 //              t1=X[j],t2=Y[j];
36             //以下是两条对角线判断。注意同一行同一个列只能判一次 
37             if(Y[j]-X[j]+i>0 && Y[j]-X[j]+i<=m && !vis[Y[j]-X[j]+i])//or vis[XXX]!=i 可以不需要重设0 
38               vis[Y[j]-X[j]+i]=1,--tmp;//printf("tmp:%d-- on line%d,colu%d
",tmp,i,X[j]-Y[j]+i);
39             if(X[j]+Y[j]-i>0 && X[j]+Y[j]-i<=m && !vis[X[j]+Y[j]-i])
40               vis[X[j]+Y[j]-i]=1,--tmp;//printf("tmp:%d-- on line%d,colu%d
",tmp,i,X[j]+Y[j]-i);
41             //列 
42             if(!vis[Y[j]])
43               vis[Y[j]]=1,--tmp;//printf("tmp:%d-- on line%d,colu%d
",tmp,i,Y[j]);
44             if(!tmp)
45               break;
46         }
47         memset(vis,0,sizeof vis);
48         Ans+= tmp;
49 //        printf("On line%d Ans:%d
",i,Ans);
50     }
51     printf("%d",Ans);
52     return 0;
53 }