搜索题大赏

P2105 K皇后

题目描述

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

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

思路

对于任意一个放在 $(x,y)$ 的皇后，它的这一行、这一列、两条对角线就要被标记为不合法。对于四种情况分别记录：

1. 每一行：$line[y]=1$
2. 每一列：$row[x]=1$
3. 从左下到右上 // 的对角线：不难发现，$x+y$ 是个定值，其实它的函数解析式可抽象为 $y=-x+b$ 。
4. 从左上到右下 \\ 的对角线：$x-y$ 是个定值。注意细节： $x-y$ 可能为负数。我们将其向右偏移一定的值（$n+m$）即可。

核心代码

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++;
		}
	}
}

数据范围是 $2 \times 10^4$ ，稍加优化一下可以卡过。

P1784 数独

题目描述

数独是根据 $9 \times 9$ 盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含 $1 - 9$ ，不重复。每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。

芬兰一位数学家号称设计出全球最难的“数独游戏”，并刊登在报纸上，让大家去挑战。

这位数学家说，他相信只有“智慧最顶尖”的人才有可能破解这个“数独之谜”。

据介绍，目前数独游戏的难度的等级有一到五级，一是入门等级，五则比较难。不过这位数学家说，他所设计的数独游戏难度等级是十一，可以说是所以数独游戏中，难度最高的等级。他还表示，他目前还没遇到解不出来的数独游戏，因此他认为“最具挑战性”的数独游戏并没有出现。

思路

考虑朴素的深搜暴力枚举。对于每一个格子，如果添过就跳过；否则枚举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;
}