【组队赛#5】BNU 4299 God Save the i-th Queen (数组映射)

【题目链接】​​click here~~​​

【题目大意】给你一个N*M的棋盘，并且给定T个已经固定位置的皇后（横坐标，纵坐标已知），求下一个合法放置皇后的可能数

【解题思路】

因为只是求下一个皇后的位置，而不是求所有其他可能，因此可以按照如下思路进行：

对n*n的矩阵进行映射，将其转换为1*(n+m)的单行模式。     1、行列可以直接映射。     2、对于对角线有两种情况（画图验证）     1.1.映射为x+y模式（一三区间）     2..1映射为x-y+Y模式(二四区间)  (注意！前面的x是映射的行，Y后才是列)

代码

/* Author:HRW 对n*n的矩阵进行映射，将其转换为1*(n+m)的单行模式。 1、行列可以直接映射。 2、对于对角线有两种情况（画图验证） 1.映射为x+y模式（一三区间） 2.映射为x-y+Y模式(二四区间) (注意！前面的x是映射的行，Y后才是列)*/#include using namespace std;typedef long long LL;const int maxn = 30000 + 10;int usedx[maxn], usedy[maxn], usedl[maxn+maxn],usedr[maxn+maxn];//int shuru()//{// int sum=0;// char ch;// while((ch=getchar())<'0'||ch>'9'); sum=ch-'0';// while((ch=getchar())>='0'&&ch<='9') sum=sum*10+ch-'0';// return sum;//}int main(){ int X,Y,N; while(cin >> X >> Y >> N,X) { memset(usedl,0,sizeof(usedl)); memset(usedr,0,sizeof(usedr)); memset(usedx,0,sizeof(usedx)); memset(usedy,0,sizeof(usedy)); for(int i = 0; i < N; ++i){ int x,y; cin>>x>>y; ++usedx[x]; //映射行 ++usedy[y]; //映射列 ++usedl[Y+x-y]; //2，4区间 ++usedr[x+y]; //1，3区间 } LL ans = 0; for(int i = 1; i <= X; ++i){ for(int j = 1; j <= Y; ++j){ if(!usedx[i] && !usedy[j] && !usedl[i-j+Y] && !usedr[i+j]) ans++; } } cout << ans << endl; } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。