无穷大？ 
搜索题大赏
P2105 K皇后
题目描述
小 Z 最近捡到了一个棋盘，他想在棋盘上摆放 个皇后。他想知道在他摆完这 个皇后之后，棋盘上还有多少个格子是不会被攻击到的。
注意：一个皇后会攻击到这个皇后所在的那一行，那一列，以及两条对角线。
思路
对于任意一个放在 的皇后，它的这一行、这一列、两条对角线就要被标记为不合法。对于四种情况分别记录：
- 每一行：
- 每一列：
- 从左下到右上
//的对角线：不难发现， 是个定值，其实它的函数解析式可抽象为 。 - 从左上到右下
\\的对角线： 是个定值。注意细节： 可能为负数。我们将其向右偏移一定的值（）即可。
核心代码
for(int i=1;i<=n;i++){ if(rx[i])continue; for(int j=1;j<=m;j++){ if(ppp[i+j]||mmm[i-j+maxn]||rx[i]||ry[j]){ ; }else{ cnt++; } }}数据范围是 ，稍加优化一下可以卡过。
P1784 数独
题目描述
数独是根据 盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含 ，不重复。每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。
芬兰一位数学家号称设计出全球最难的“数独游戏”，并刊登在报纸上，让大家去挑战。
这位数学家说，他相信只有“智慧最顶尖”的人才有可能破解这个“数独之谜”。
据介绍，目前数独游戏的难度的等级有一到五级，一是入门等级，五则比较难。不过这位数学家说，他所设计的数独游戏难度等级是十一，可以说是所以数独游戏中，难度最高的等级。他还表示，他目前还没遇到解不出来的数独游戏，因此他认为“最具挑战性”的数独游戏并没有出现。
思路
考虑朴素的深搜暴力枚举。对于每一个格子，如果添过就跳过；否则枚举1～9，并检验其行、列、九宫格是否合法。
优化一下，我们不对每一个格子都去判断合不合法，而是在填充一个格子的时候记录下不合法的状态，可以省去一些复杂度。
以下两个函数就是用来记录被BAN的和解除封印：
int forbbiden[maxn+1][maxn+1][maxn+1];void forbbid(int x,int y,int num){ for(int k=1;k<=maxn;k++){ forbbiden[x][k][num]++; forbbiden[k][y][num]++; } int len=maxn/3; int sx=(int(ceil(1.0*x/len))-1)*len+1; int sy=(int(ceil(1.0*y/len))-1)*len+1; for(int i=sx;i<=sx+len-1;i++){ for(int j=sy;j<=sy+len-1;j++){ forbbiden[i][j][num]++; } }}void unforbbid(int x,int y,int num){ for(int k=1;k<=maxn;k++){ forbbiden[x][k][num]--; forbbiden[k][y][num]--; } int len=maxn/3; int sx=(int(ceil(1.0*x/len))-1)*len+1; int sy=(int(ceil(1.0*y/len))-1)*len+1; for(int i=sx;i<=sx+len-1;i++){ for(int j=sy;j<=sy+len-1;j++){ forbbiden[i][j][num]--; } }}然后就是简单的dfs算法：
pair <int,int> nxt(int i,int j){ int x=i,y=j; if(y==maxn){ y=1,x++; }else{ y++; } return {x,y};}void dfs(int x,int y){ if(x==maxn+1){ output(); exit(0); } if(board[x][y]){ dfs(nxt(x,y).first,nxt(x,y).second); return; } for(int num=1;num<=maxn;num++){ if(!forbbiden[x][y][num]){ board[x][y]=num; forbbid(x,y,num); dfs(nxt(x,y).first,nxt(x,y).second); board[x][y]=0; unforbbid(x,y,num); } }}主函数别忘了在输入的时候也要记录不合法：
int main(){ for(int i=1;i<=maxn;i++){ for(int j=1;j<=maxn;j++){ board[i][j]=read(); forbbid(i,j,board[i][j]); } } dfs(1,1); return 0;}八数码难题
题目描述
在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
代码
这道题主要学习一下如何让代码更加简明。
#include <bits/stdc++.h>using namespace std;string st;struct node{ string status; int step;};map <string,bool> vis;const pair<int,int> swapRule[]={ {1,2},{1,4},{2,3},{2,5},{3,6}, {4,5},{4,7},{5,6},{5,8},{6,9}, {7,8},{8,9}};void print(string s){ cout<<s[0]<<s[1]<<s[2]<<endl; cout<<s[3]<<s[4]<<s[5]<<endl; cout<<s[6]<<s[7]<<s[8]<<endl; cout<<endl;}int main(){ cin>>st; if(st=="123804765"){ cout<<0; return 0; } queue <node> q; q.push(node{st,0}); vis[st]=1; while(!q.empty()){ node fnt=q.front(); q.pop(); for(int i=0;i<12;i++){ int a=swapRule[i].first-1,b=swapRule[i].second-1; if(fnt.status[a]=='0'||fnt.status[b]=='0'){ swap(fnt.status[a],fnt.status[b]); if(fnt.status=="123804765"){ cout<<fnt.step+1; return 0; } if(!vis[fnt.status]){ q.push({fnt.status,fnt.step+1}); vis[fnt.status]=1; } swap(fnt.status[a],fnt.status[b]); } } } return 0;}支持与分享
如果这篇文章对你有帮助，欢迎分享给更多人或赞助支持！