本文详细介绍了各种搜索算法，包括宽度优先搜索（BFS）、深度优先搜索（DFS）、A*算法、双向搜索等，并通过实例解析了它们在解决实际问题中的应用，如迷宫问题、八数码问题、字串接龙等。文章强调了搜索过程中的剪枝与优化策略，以及如何设计合适的估价函数来提高效率。
搜索
本来是在学斜率优化DP。。。结果好难啊，我放弃了，先学会搜索放松放松（
BFS
Flood Fill模型
Flood Fill模型就听起来好像很牛逼，其实我们刚学搜索应该就见过这样的题型，中文名叫泛洪算法，也叫种子填充(Seed Fill)，用于确定连接到多维数组中给定节点的区域。这么说也许比较抽象，我们看例题后就知道这是个什么玩意了。
池塘计数
题目链接：池塘计数
分析：这道题还是比较简单的，我们从第一行第一列开始依次往后搜，搜到W时，池塘数++，然后把与这个W相连通的所有W改为.（包括这个W自身），最终池塘数就是答案。
代码实现：
#include<iostream>
#define x first
#define y second
using namespace std;
const int N=1010,M=N*N;
int n,m;
char g[N][N];
int ans;
typedef pair<int,int> PII;
PII q[M];
void bfs(int x,int y){
int hh=0,tt=-1;
q[++tt]={x,y};
g[x][y]='.';
while(hh<=tt){
auto tmp=q[hh++];
int x1=tmp.x,y1=tmp.y;
for(int i=x1-1;i<=x1+1;i++){
for(int j=y1-1;j<=y1+1;j++){
if(i>=0&&i<n&&j>=0&&j<m&&g[i][j]=='W'){
g[i][j]='.';
q[++tt]={i,j};
}
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++){
scanf("%s",g[i]);
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(g[i][j]=='W'){
bfs(i,j);
ans++;
}
}
}
printf("%d",ans);
return 0;
}
城堡问题
题目链接：城堡问题
分析：对于这道题，除了要求面积外和上题一模一样，因此我们给bfs加个返回值就行了，对于这个墙壁表示，我们发现，如果把这个数字分解为二进制，假设最低位是第0位，第0位是1就代表有西墙，第1位是1就代表有北墙，第2位是1就代表有东墙，第3位是1就代表有南墙，我们定义偏移数组时就按照这个顺序来定义，会很方便。
代码实现：
#include<iostream>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
int n,m;
const int N=55;
int d[4][2]={{0,-1},{-1,0},{0,1},{1,0}};//偏移数组也按照这个顺序定义
int g[N][N];
int area,ans;
PII q[N*N];
bool vis[N][N];
int bfs(int sx,int sy){//返回面积
int area=0;
vis[sx][sy]=1;
int hh=0,tt=0;
q[0]={sx,sy};
while(hh<=tt){
auto tmp=q[hh++];
area++;//统一都在出队的时候加上，不重不漏
for(int i=0;i<4;i++){
int x=tmp.x+d[i][0],y=tmp.y+d[i][1];
if(x<0||x>=n||y<0||y>=m||vis[x][y]||g[tmp.first][tmp.second]>>i&1) continue;
q[++tt]={x,y};
vis[x][y]=1;
}
}
return area;
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>g[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(vis[i][j]) continue;
area=max(area,bfs(i,j));//更新面积
ans++;
}
}
cout<<ans<<endl<<area;
return 0;
}
山峰和山谷
题目链接：山峰和山谷
分析：这道题还是比较有意思的，和上面的题（太水了）相比有了一些思维上的难度，其实我们在搜索的时候是会搜到相邻的高度不同的地方的，我们设高度相同的为一个连通块，我们只需传参时再传两个bool型变量has_lower和has_higher，如果有比这个连通块高度高的，就把has_higher置为true，has_lower同理，然后搜完再判断，如果has_lower为false，说明没有比这个连通块低的，说明山谷数要++，has_higher同理。
代码实现：
#include<iostream>
#define x first
#define y second
using namespace std;
int n;
int peak,valley;
const int N=1010;
typedef pair<int,int> PII;
PII q[N*N];
int g[N][N];
bool vis[N][N];
int hh,tt;
void bfs(int x,int y,bool& has_higher,bool& has_lower){
vis[x][y]=1;
hh=tt=0;
q[0]={x,y};
while(hh<=tt){
auto t=q[hh++];
int a=t.x,b=t.y;
for(int i=a-1;i<=a+1;i++){
for(int j=b-1;j<=b+1;j++){
if(i<1||i>n||j<1||j>n) continue;//越界就continue
if(g[i][j]>g[a][b]){//如果比它高
has_higher=true;//置为true
}
else if(g[i][j]<g[a][b]){//如果比它低
has_lower=true;//置为true
}
else if(!vis[i][j]){//或者是同等高度却没搜过，就加入队列
vis[i][j]=1;
q[++tt]={i,j};
}
}
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&g[i][j]);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(vis[i][j]) continue;
bool has_higher=false,has_lower=false;
bfs(i,j,has_higher,has_lower);
//由于一片区域可以既是山峰又是山谷，所以这样写非常舒服
if(!has_higher) peak++;
if(!has_lower) valley++;
}
}
cout<<peak<<" "<<valley;
return 0;
}
最短路模型
最短路模型也是我们非常常见的一个模型，难度应该较低吧。。。（希望如此），我们还是通过例题来学习。
迷宫问题
题目链接：迷宫问题
分析：一般求边权相等的最短路径、最少操作次数都可以用bfs来求解，这种题太常见了，我就不细细讲解了。本题还需要打印路径，我们只需再开一个二维数组，记录每一个点是由哪一个点转移而来的就行了，但是那样的话我们好像只能从后往前打印（递归的话能实现从前往后打印），我们换一个角度思考，我们让它从终点走到起点，这样是等价的，而且打印的时候就能直接正向递推打印了。
代码实现：
#include<iostream>
#include<cstring>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
int n;
const int N=1010;
int g[N][N];
PII pre[N][N];
PII q[N*N];
int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void bfs(){
int hh=0,tt=0;
q[0]={n-1,n-1};
while(hh<=tt){
auto t=q[hh++];
for(int i=0;i<4;i++){
int x=t.first+d[i][0],y=t.second+d[i][1];
if(x<0||x>=n||y<0||y>=n||pre[x][y].x!=-1||g[x][y]) continue;//这里判断不能往回搜的时候可以直接用pre数组了，不用再多开一个bool数组了
q[++tt]={x,y};
pre[x][y]=t;
}
}
}
int main(){
memset(pre,-1,sizeof pre);
scanf("%d",&n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%d",&g[i][j]);
}
}
bfs();
PII ed(0,0);//从0，0开始打印
while(1){
printf("%d %d\n",ed.x,ed.y);
if(ed.x==n-1&&ed.y==n-1) break;//如果到终点就break
ed=pre[ed.x][ed.y];//否则就找到上一个点
}
return 0;
}
武士风度的牛
题目链接：武士风度的牛
分析：名叫The Knight的牛，这让我想起来《空洞骑士》这款优秀的游戏，其实这两者之间没有任何联系，我只是想向你安利这个游戏而已。这道题和上面的题其实本质一样，只不过换了一种走法，变成了马走日，第一个走到的位置就是花费最小步数能走到的。
代码实现：
#include<iostream>
#include<cstring>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
int n,m;
const int N=160;
char g[N][N];
int dis[N][N];//dis[i][j]表示牛跳到i，j这个位置所需的最小步数
PII q[N*N];
int d[8][2]={{2,1},{2,-1},{1,2},{1,-2},{-1,2},{-1,-2},{-2,1},{-2,-1}};//8种走法
int bfs(){
int ans=0;
int hh=0,tt=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(g[i][j]=='K'){//找到K的位置，并把距离初始化为0
q[hh]={i,j};
dis[i][j]=0;
break;
}
}
}
while(hh<=tt){
auto t=q[hh++];
for(int i=0;i<8;i++){
int x=t.x+d[i][0],y=t.y+d[i][1];
if(x<0||x>=n||y<0||y>=m||dis[x][y]!=-1||g[x][y]=='*') continue;
dis[x][y]=dis[t.x][t.y]+1;
q[++tt]={x,y};
if(g[x][y]=='H') return dis[x][y];
}
}
}
int main(){
memset(dis,-1,sizeof dis);//先把所有距离初始化为-1，还能代表这个点没走过
cin>>m>>n;
for(int i=0;i<n;i++){
cin>>g[i];
}
cout<<bfs();
return 0;
}
抓住那头牛
题目链接：抓住那头牛
分析：一维坐标上的bfs，还是比较简单的，而这里有个跳到2*x坐标的操作，如果不放心可以把数组开成二倍，实际上开成1倍就行了，跳出界的一定不是唯一的最优解，自己想想吧！
代码实现：
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+10;
int n,k,q[N],dis[N];//dis记录距离，为-1时表示没到过此点
int bfs(){
memset(dis,-1,sizeof dis);
q[0]={n};
dis[n]=0;
int hh=0,tt=0;
while(hh<=tt){
auto t=q[hh++];
if(t==k) return dis[t];//可以在出队时判定并返回，也可以在下面的if语句中判断，不过那样就得写三遍了，我比较懒
if(t-1>=0&&dis[t-1]==-1){
dis[t-1]=dis[t]+1;
q[++tt]=t-1;
}
if(t+1<N&&dis[t+1]==-1){
dis[t+1]=dis[t]+1;
q[++tt]=t+1;
}
if(t*2<N&&dis[t*2]==-1){
dis[t*2]=dis[t]+1;
q[++tt]=2*t;
}
}
}
int main(){
cin>>n>>k;
cout<<bfs();
return 0;
}
多源BFS
多源BFS就是从多个点出发去搜，但是还是保证了第一次搜到时的结果最小，可以解决一些比较有意思的问题。
矩阵距离
题目链接：矩阵距离
分析：我们只需把所有值为1的位置加入队列，然后从这些1出发，就能求出道每个点的最短曼哈顿距离。
代码实现：
#include<iostream>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=1010;
int n,m,g[N][N],hh=0,tt=-1,d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
PII q[N*N];
bool vis[N][N];
void bfs(){
while(hh<=tt){
auto t=q[hh++];
for(int i=0;i<4;i++){
int x=t.x+d[i][0],y=t.y+d[i][1];
if(x<1||x>n||y<1||y>m||vis[x][y]) continue;
vis[x][y]=1;
g[x][y]=g[t.x][t.y]+1;
q[++tt]={x,y};
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%1d",&g[i][j]);
if(g[i][j]==1){//对于为1的点
q[++tt]={i,j};//加入队列中
g[i][j]=0;//值赋为0
vis[i][j]=1;//标记为搜过了
}
}
}
bfs();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
printf("%d ",g[i][j]);
}
puts("");
}
return 0;
}
最小步数模型
除了走路的最短路，我们还可以用bfs求到达某一状态的最少操作步数，这种题目往往也有套路，比较简单（难的是剪枝）。
魔板
题目链接：魔板
分析：要让我们求字典序最小的操作序列，那我们应该优先用A操作，其次用B操作，最后用C操作，这样得到的一定是字典序最小的。但这题真的好恶心啊，都是一些细节的处理，看代码的详细注释吧。
代码实现：
#include<iostream>
#include<unordered_map>
#include<queue>
using namespace std;
unordered_map<string,int> dis;//dis记录每个字符串对应的操作步数
unordered_map<string,pair<char,string>> pre;//pre记录每个字符串是由哪个字符串通过哪个操作转化而来的
string str,ed;
char g[2][4];//g数组用来执行相关变换
void print(string tmp){
if(tmp==str) return ;
print(pre[tmp].second);
cout<<pre[tmp].first;
}
void set(string tmp){
for(int i=0;i<4;i++){
g[0][i]=tmp[i];
}
for(int i=7;i>3;i--){
g[1][7-i]=tmp[i];
}
}
string get(){
string ans;
for(int i=0;i<4;i++){
ans+=g[0][i];
}
for(int i=3;i>-1;i--){
ans+=g[1][i];
}
return ans;
}
string move0(string tmp){//A转换方法
set(tmp);//将tmp字符串拆分到g数组中，执行相关操作，后面的几个函数同理
for(int i=0;i<4;i++) swap(g[0][i],g[1][i]);
return get();//执行完后，将g中状态拼成字符串返回
}
string move1(string tmp){//B转换方法
set(tmp);
char a=g[0][3],b=g[1][3];
for(int i=2;i>=0;i--){
g[0][i+1]=g[0][i];
g[1][i+1]=g[1][i];
}
g[0][0]=a,g[1][0]=b;
return get();
}
string move2(string tmp){//C转换方法
set(tmp);
char a=g[0][1];
g[0][1]=g[1][1];
g[1][1]=g[1][2];
g[1][2]=g[0][2];
g[0][2]=a;
return get();
}
int bfs(string str,string ed){
if(str==ed){
return 0;
}
queue<string> q;
q.push(str);
dis[str]=0;
while(q.size()){
auto t=q.front();
q.pop();
string m[3];//记录三种转换后的字符串
m[0]=move0(t);
m[1]=move1(t);
m[2]=move2(t);
for(int i=0;i<3;i++){
if(!dis[m[i]]){//第一次转换到这个状态
dis[m[i]]=dis[t]+1;
pre[m[i]]={'A'+i,t};
q.push(m[i]);
if(m[i]==ed) return dis[ed];//如果完成，就立即返回
}
}
}
}
int main(){
int x;
for(int i=0;i<8;i++){
cin>>x;
ed+=x+'0';//目标状态
}
str="12345678";//起始状态
cout<<bfs(str,ed)<<endl;
print(ed);//递归打印
return 0;
}
双端队列广搜
对于一种距离只有0和1的走法，我们可以用双端队列广搜来求出最短路，如果距离为0，新的状态就从队列的头部插入，否则从尾部插入，由于一个点可能出队两次，但是只有最短的那一个更新的值才是正确的，因此我们只在队列中的数出队的时候判断是否已经搜过，最终得到的答案也是正确的。
电路维修
题目链接：电路维修
分析：如图，我们这样设出点的坐标，我们容易得到，只有横纵坐标和为偶数的点才能到达，因为沿着斜线走横纵坐标和的变化是偶数，而起始点的横纵坐标和也是偶数。方格左边便以格子的右下角表示，图中红色的是方格坐标，蓝色的是点坐标。
另外，对于方格坐标的变化，如果我们以另一个数组记录，就能比较容易的写出最终答案（就按照双端队列广搜的套路）。
代码实现：
#include<iostream>
#include<cstring>
#include<deque>
using namespace std;
int r, c;
const int N = 510;
char g[N][N];
int dis[N][N];//dis[i][j]表示i，j到0，0的最少操作步数
bool vis[N][N];
int d[4][2] = { {-1,-1},{-1,1},{1,1},{1,-1} };//沿着四种斜线走的左边变化，分别是左上，右上，右下，左下
int s[4][2] = { {-1,-1},{-1,0},{0,0},{0,-1} };//s是沿着四条斜线后坐标点的变化，注意与上面的对应，这个可以自己设个点模拟一下，就能退出相应的变化
char check[5] = "\\/\\/";//由于\经常用于转义字符，因此要表示\需要写成\\这样，这里也要注意与上面的方向保持一致
void bfs() {
memset(dis, 0x3f, sizeof dis);//初始化为很大的数
memset(vis, 0, sizeof vis);
dis[0][0] = 0;//起始点初始化为0
deque<pair<int, int>> q;
q.push_back({ 0,0 });
while (q.size()) {
auto t = q.front();
q.pop_front();
if (vis[t.first][t.second]) continue;//如果更新过，就不能再用它更新了
vis[t.first][t.second] = 1;
for (int i = 0; i < 4; i++) {
int x = t.first + d[i][0], y = t.second + d[i][1];//到达点的坐标
if (x<0 || x>r || y<0 || y>c) continue;
int a = t.first + s[i][0], b = t.second + s[i][1];//格子的左边，主要用于比对斜线方向是否一致
int tmp = dis[t.first][t.second] + (check[i] != g[a][b]);//不一致距离就要+1
if (tmp < dis[x][y]) {//如果距离小于当前距离，更新
dis[x][y] = tmp;
if (g[a][b] != check[i]) q.push_back({ x,y });//如果是方向不一致的，说明多用了一个距离，加到队尾
else q.push_front({ x,y });//否则加到队首
}
}
}
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &r, &c);
for (int i = 0; i < r; i++) {
scanf("%s", g[i]);//我们以每个方格的右下角代表这个方格的左边
}
if ((r + c) % 2) puts("NO SOLUTION");//如果是奇数，无解
else {
bfs();
printf("%d\n", dis[r][c]);//从0，0点到r，c点的最短距离
}
}
return 0;
}
双向广搜
这又是个什么东西呢？让我们先看例题，从朴素的搜索解决问题的局限中来提炼出来双向广搜。
字串变换
题目链接：字串变换
分析：这一题中，我们可以直接暴力搜索，字符串长度最大为20，而最多有6中变换方式，假设每个字符都能变换，那么每扩展一层状态数就会扩大120倍，毫无疑问是会TLE/MLE的，原因就在于每扩展一层，状态数的变化太大。这道题我们发现我们从起点搜到终点这种方法好像走不通，但是我们再想，我们可以从起点和终点同时往中间搜，这样就是两个方向分别扩大120倍但扩大的次数变为了原来的一半，妙啊！但是我们还要注意（不是这一题中的情况，但以后有可能遇到），有可能从起点搜的状态扩大的速度远大于从终点搜扩大的速度，那我们就需要多从终点搜，少从起点搜，比较好的方法就是看哪个状态数量少就搜哪个，这也是一个优化，具体细节见代码。
代码实现：
#include<iostream>
#include<unordered_map>
#include<queue>
using namespace std;
const int N=6;
int n;
string a[N],b[N];
unordered_map<string,int> da,db;//用哈希表记录到每个字符串的操作步数，da记录从起点到的，db记录从终点到的
queue<string> qa,qb;//qa存放从起点搜的，qb存放从终点搜的
string str,ed;
//注意对数组的引用写法是string(&a)[N]
int extend(queue<string> &q,unordered_map<string,int>&da,unordered_map<string,int>&db,string(&a)[N],string(&b)[N]){//只扩展一层
int d=da[q.front()];
while(q.size()&&da[q.front()]==d){//保证只扩展一层
auto t=q.front();
q.pop();
for(int i=0;i<n;i++)//考虑n中变换方法
for(int j=0;j<t.size();j++)//这里就不用kmp了，反正数据范围很小
if(t.substr(j,a[i].size())==a[i]){
string ans=t.substr(0,j)+b[i]+t.substr(j+a[i].size());//替换后的字符串
if(da.count(ans)) continue;//如果更新过了就不更新了，这样才能保证是最短的
da[ans]=da[t]+1;
if(db.count(ans)) return da[ans]+db[ans];//如果两边都搜到了，返回距离之和
q.push(ans);
}
}
return 11;//否则返回一个大于10的数
}
int bfs(){
if(str==ed) return 0;
qa.push(str);
qb.push(ed);
da[str]=db[ed]=0;
int step=0;
while(qa.size()&&qb.size()){//只要有一个为空就说明不可能
int t=0;
if(qa.size()<=qb.size()) t=extend(qa,da,db,a,b);//用qa扩展
else t=extend(qb,db,da,b,a);//用qb扩展，注意从终点扩展是从b到a，哈希表位置也要反一下
if(t<=10) return t;
if(++step==10) return 11;//假如已经到了10步还没找到答案，返回11（任意一个大于10的数）
}
return 11;//搜完了也没找到，返回11
}
int main(){
cin>>str>>ed;
while(cin>>a[n]>>b[n]) n++;//题目没给我们具体的变换方案数，我们这样写
int ans=bfs();
if(ans>10) puts("NO ANSWER!");
else cout<<ans<<endl;
return 0;
}
A*
A*算法是个什么意思呢？我们先来考虑一些问题，比如说八数码问题，我们直接暴力搜索的话状态数量非常多，我们有什么方法可以优化吗？这里就用到了A*算法，我们给每一个状态按照一定的计算方法求出来它到终点距离的估计值（满足这个估计值一定小于等于真实距离才能保证正确性），然后我们每次取队列中到原点真实值和到终点估计值之和最小的数来扩展，当终点出队时，它到原点的真实值一定是最小的。(假设不是最小的，那么一定有到原点真实距离与到终点估计距离更小的点，因为到终点的估计距离小于等于实际距离，这个终点就不会出队列)。按这样的方法计算我们会少遍历很多状态，因此是一个不错的优化。另外，如果题目无解的话，用A *算法会更慢，另外，用此算法是允许有负权边的，但不能有负权环。因此，我们的难题就在于设计一个函数来求到终点的估计距离，很多时候这并不需要我们自己来设计，因为考到的基本都是前人已经创造出来过的，我们需要先了解前人设计的函数，同时这也会启发我们自己设计函数。另外还有一点，该方法只能保证终点出队时的值是最小的，其它点都不能。
举例：图中边权都是1
入度为0的点是起点，出度为0的点是终点。自己试试吧。
八数码
题目链接：八数码
提示：这题也可以用双向广搜来写哦。
分析：两个问题，一、我们需要找出一个函数满足求出某个状态到终点状态的估计距离并且该估计距离小于真实距离，对于该题来说，我们对照现在该状态和终点状态的两个3*3的格子，把当前状态每个点到它应该到的位置的哈密顿距离相加，就是这样一个估计距离，因为要想移动点必须让x与它交换，而对于每个点都是最少交换哈密顿距离次，因此这个函数是可行的。
二、判断是否有解，这个《算法竞赛进阶指南》上有讲，我们把3*3的矩阵连成一行，那么终点“12345678x”中就有0对逆序对（忽略x），我们发现，当我们让x与同一行的元素交换，逆序对数量不变，与上下列的元素交换，逆序对数量要么+2，要么-2，要么不变，因此我们的初始状态有偶数对逆序对时才有解！实际上，对于所有奇数*奇数的该类问题都是如此，而对于偶数 *偶数的问题，只有当逆序对的奇偶性与两个状态中x行数之差的奇偶性相同时才有解（感兴趣的可以自行推导），而上面只是证明了必要性，并未证明充分性，充分性证明较难，这里就不多bb了（我不会）。
代码实现：（细节较多，100ms，还是很快的）
#include<iostream>
#include<unordered_map>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,string> PIS;
unordered_map<string,int> dist;//记录到每一个字符串的距离
unordered_map<string,pair<char,string>> pre;//记录每个字符串的前一个字符串以及操作
int d[4][2]={{-1,0},{0,-1},{1,0},{0,1}};//上左下右
char s[4]={'u','l','d','r'};//对应好4个方向
int g(string str){//求出g状态到终点的估计值
int res=0;
for(int i=0;i<str.size();i++)
if(str[i]!='x'){
int t=str[i]-'1';
res+=abs(i/3-t/3)+abs(i%3-t%3);
}
return res;
}
void astar(string str){
string ed="12345678x";
dist[str]=0;
priority_queue<PIS,vector<PIS>,greater<PIS>> heap;//存储到起点的真实距离和到终点的估计距离之和和字符串
heap.push({g(str),str});
while(heap.size()){
auto t=heap.top();
heap.pop();
string state=t.second;
if(state==ed) break;//到终点就break
int step=dist[state];//记录下来到现在的步数
int x,y;
for(int i=0;i<state.size();i++)
if(state[i]=='x'){
x=i/3,y=i%3;
break;
}
string sour=state;//备份一份，下面要用
for(int i=0;i<4;i++){//向四个方向交换
int a=x+d[i][0],b=y+d[i][1];
if(a>=0&&a<3&&b>=0&&b<3){
swap(state[x*3+y],state[a*3+b]);
if(!dist.count(state)||dist[state]>step+1){//如果这个状态没被搜过或者说当前搜到的距离更小
dist[state]=step+1;//更新距离
pre[state]={s[i],sour};//记录前驱
heap.push({dist[state]+g(state),state});//加入堆中
}
swap(state[x*3+y],state[a*3+b]);//恢复现场
}
}
}
string res;//存储答案
while(ed!=str){
res+=pre[ed].first;
ed=pre[ed].second;
}
reverse(res.begin(),res.end());//因为是倒着推的，正着输出的话需要再reverse
cout<<res;
}
int main(){
string str,s;
for(int i=0;i<9;i++){
string tmp;
cin>>tmp;
if(tmp!="x") s+=tmp;
str+=tmp;
}
int cnt=0;
for(int i=0;i<8;i++)//求逆序对数量
for(int j=i+1;j<8;j++)
if(s[i]>s[j]) cnt++;
if(cnt%2) cout<<"unsolvable";
else astar(str);
return 0;
}
第k短路
题目链接：第k短路
分析：从上面接着想，终点第一次出队时是最短路，第k次出队时会不会就是第k短路呢？答案是对的，证明和上面类似，就不赘述了，而这道题我们要求估计的到终点距离，那我们直接反向建边跑一遍dijkstra算法就求出来所有点到终点的最短距离了，而这个最短距离肯定也小于等于真实的第2~k短距离，因此是正确的。
代码实现：
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=1010,M=2e4+10;//反向建边需要二倍的边数
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
int dist[N],h[N],rh[N],idx=1,e[M],ne[M],w[M];//rh就是反向建边的头结点
int n,m,S,T,K,a,b,c,cnt;
bool st[N];
void add(int* h,int a,int b,int c){
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void dijkstra(){
priority_queue<PII,vector<PII>,greater<PII>> heap;
memset(dist,0x3f,sizeof dist);
dist[T]=0;
heap.push({0,T});
while(heap.size()){
auto t=heap.top();
heap.pop();
int u=t.second;
if(st[u]) continue;
st[u]=1;
for(int i=rh[u];i;i=ne[i]){
int j=e[i];
if(dist[j]>dist[u]+w[i]){
dist[j]=dist[u]+w[i];
heap.push({dist[j],j});
}
}
}
}
int astar(){
priority_queue<PIII,vector<PIII>,greater<PIII>> heap;
heap.push({dist[S],{0,S}});//分别是{到起点的真实值与到终点的估计值之和,{到起点的真实值,编号}}
if(dist[S]==0x3f3f3f3f) return -1;//特判一下S与T不连通的情况
while(heap.size()){
auto t=heap.top();
heap.pop();
int u=t.second.second,dis=t.second.first;
if(u==T) cnt++;
if(cnt==K) return dis;
for(int i=h[u];i;i=ne[i]){
int j=e[i];
heap.push({dis+w[i]+dist[j],{dis+w[i],j}});
}
}
return -1;//该节点不能被访问K次
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>a>>b>>c;
add(h,a,b,c);
add(rh,b,a,c);//反向建边
}
cin>>S>>T>>K;
if(S==T) K++;//如果起终点相同，0会被算最短路，但我们并不存在这条路，因此就求k+1短路
dijkstra();//反向跑dijkstra
cout<<astar();
return 0;
}
DFS
DFS与连通性模型
迷宫
题目链接：迷宫
这题用bfs也能做，这里用dfs来实现，注意：本题中每个点只搜一遍，因此不会有恢复现场这一步，另外，这里dfs求不了求最短路，只能求出连通性。不过dfs的代码更短，更好写。
代码实现：
#include <cstring>
#include <iostream>
using namespace std;
const int N = 110;
int n;
char g[N][N];
int sx, sy, ex, ey;//sx,sy为起点坐标，ex,ey为终点坐标
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };
bool st[N][N];
bool dfs(int x, int y) {
if (g[x][y] == '#') return false;
if (x == ex && y == ey) return true;
st[x][y] = true;
for (int i = 0; i < 4; i++) {
int a = x + dx[i], b = y + dy[i];
if (a < 0 || a >= n || b < 0 || b >= n) continue;
if (st[a][b]) continue;
if (dfs(a, b)) return true;
}
return false;
}
int main() {
int T;
cin >> T;
while (T--) {
cin >> n;
for (int i = 0; i < n; i++) cin >> g[i];
cin >> sx >> sy >> ex >> ey;
memset(st, 0, sizeof st);
if (dfs(sx, sy)) puts("YES");
else puts("NO");
}
return 0;
}
红与黑
题目链接：红与黑
本题也能通过bfs求解，不过还是那句话，dfs代码短，这里我们用全局变量记录数量，注意这题非常坑的一个点，先读入列，再读入行。
代码实现：
#include <cstring>
#include <iostream>
using namespace std;
const int N = 25;
int n, m;
char g[N][N];
bool st[N][N];
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };
int cnt;
void dfs(int x, int y) {
cnt++;
st[x][y] = true;
for (int i = 0; i < 4; i++) {
int a = x + dx[i], b = y + dy[i];
if (a < 0 || a >= n || b < 0 || b >= m) continue;
if (g[a][b] != '.') continue;
if (st[a][b]) continue;
dfs(a, b);
}
}
int main() {
while (cin >> m >> n, n || m) {
cnt = 0;//记得清0
for (int i = 0; i < n; i++) cin >> g[i];
int x, y;
for (int i = 0; i < n; i++)//找到开始位置
for (int j = 0; j < m; j++)
if (g[i][j] == '@') {
x = i;
y = j;
}
memset(st, 0, sizeof st);
dfs(x, y);
cout << cnt << endl;
}
return 0;
}
DFS与搜索顺序
这些题主要有什么特点我也不清楚，不过写这几个题可以为后面的剪枝优化打基础。
马走日
题目链接：马走日
这题明显不难，我们只需在深搜的时候多传一个参数表示当前搜到的点数，当点数与n*m相等时，ans++，就能找出最终答案。
代码实现：
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10;
int n, m;
bool st[N][N];
int ans;
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
void dfs(int x, int y, int cnt){
if (cnt == n * m){
ans ++ ;
return;
}
st[x][y] = true;
for (int i = 0; i < 8; i ++ ){
int a = x + dx[i], b = y + dy[i];
if (a < 0 || a >= n || b < 0 || b >= m) continue;
if (st[a][b]) continue;
dfs(a, b, cnt + 1);
}
st[x][y] = false;//这里别忘了恢复现场
}
int main(){
int T;
scanf("%d", &T);
while (T -- ){
int x, y;
scanf("%d%d%d%d", &n, &m, &x, &y);
memset(st, 0, sizeof st);
ans = 0;
dfs(x, y, 1);
printf("%d\n", ans);
}
return 0;
}
单词接龙
题目链接：单词接龙
分析：这题我们爆搜就可以了，对于可以连接的两个字符串，我们当然希望重叠部分越少越好，这样连接起来才更长，这样我们就可以开始搜了。
代码实现：
#include <iostream>
using namespace std;
const int N = 21;
int n;
string word[N];
int g[N][N];//g[i][j]表示第i个字符串的前缀和第j个字符串的后缀的最大重合长度
int used[N];
int ans;
void dfs(string dragon, int last){//
ans = max((int)dragon.size(), ans);//更新答案，max只能比较两个相同类型的，因此把size_t转换为int
used[last] ++ ;//last用的次数++
for (int i = 0; i < n; i ++ )
if (g[last][i] && used[i] < 2)//二者必须有公共长度并且i用的次数小于2次
dfs(dragon + word[i].substr(g[last][i]), i);//直接拼接上i从重叠长度的下标开始往后的部分
used[last] -- ;//恢复现场
}
int main(){
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> word[i];
char start;
cin >> start;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ ){
string a = word[i], b = word[j];
for (int k = 1; k < min(a.size(), b.size()); k ++ )//枚举公共长度，不能取到a或b的长度
if (a.substr(a.size() - k, k) == b.substr(0, k)){//从小到大枚举
g[i][j] = k;//
break;//一旦找到就break，这样就是最小的
}
}
for (int i = 0; i < n; i ++ )
if (word[i][0] == start)//能接到起始字母后才搜索
dfs(word[i], i);
cout << ans << endl;//输出答案
return 0;
}
分成质数组
题目链接：分成质数组
分析：对于这道题，爆搜就可以了。即按顺序考虑每个数怎么放。
代码实现：
#include <iostream>
#include <vector>
using namespace std;
const int N = 10;
int n, a[N], ans = N, len;
int gcd(int x, int y) {//求最大公约数
return y ? gcd(y, x % y) : x;
}
vector<int> g[N];//g[i]表示第i组的数
bool check(int u, int c) {//检查u是否能放入c组中
for (int i = 0; i < g[c].size(); i++)
if(gcd(g[c][i], u) > 1) return false;
return true;
}
void dfs(int u) {
if(len >= ans) return;//加个剪枝优化
if(u == n) {//如果考虑完了n个数，就更新答案
ans = min(ans, len);
return;
}
for(int i = 0; i < len; i++) {//考虑当前有的所有组
if(check(a[u], i)) {//考虑能否放入
g[i].push_back(a[u]);
dfs(u + 1);
g[i].pop_back();//恢复现场
}
}
g[len++].push_back(a[u]);//放入新的组中
dfs(u + 1);
g[--len].pop_back();//恢复现场
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", a + i);
dfs(0);
printf("%d\n", ans);
}
DFS与剪枝与优化
我们知道：对于很多问题，我们如果直接爆搜的话状态是非常多的，这时我们通过合适的剪枝与优化能使时间复杂度大幅下降，可是我们并不能计算出时间复杂度。一般来说，常用的优化与剪枝策略如下：
- 优化搜索顺序
按照不同的顺序搜索，我们所花的时间可能不同，这个优化的侧重点就是让我们找到更快的搜索顺序。 - 排除等效冗余
这个比较容易理解，比如说求解组合问题，我们如果枚举排序数就会重复枚举好多遍某个状态，这时枚举组合数就会大大优化时间。 - 可行性剪枝
顾名思义，当我们搜到某个状态已经不合题意时，就直接终止 - 最优性剪枝
当前策略无法更新答案，直接终止 - 记忆化（这个我们主要是在dp中讲的，这里就不侧重于它了）
小猫爬山
题目链接：小猫爬山
分析：很明显，这道题我们只需枚举每只小猫放在第几个车里就行了，但是状态数量还是非常多的，因此我们需要剪枝并优化，相关内容见代码。
代码实现：
也就跑了20ms左右，还是非常快的。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N=20;
int sum[N],w[N],n,tot,ans;
void dfs(int x,int y){//y代表车的数量
if(y>=ans) return ;//如果当前车的数量已经大于等于ans，就没必要搜了
if(x==n) {//考虑完了n个物品，因为y>=ans的情况已经剪掉了，因此这里一定可以更新
ans=y;
return ;
}
for(int i=0;i<y;i++)//考虑前y个车，即第0~y-1个车
if(sum[i]+w[x]<=tot){
sum[i]+=w[x];//放入第i个车
dfs(x+1,y);//考虑下一个物品
sum[i]-=w[x];//恢复现场
}
sum[y]=w[x];//放入第y个车
dfs(x+1,y+1);//车的数量++，考虑下一个物品
sum[y]=0;//恢复现场
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>tot;
ans=n;
for(int i=0;i<n;i++) cin>>w[i];
sort(w,w+n,greater<int>());//从大到小排序，因为先考虑体重大的猫咪的话搜索数量肯定比先考虑体重小的猫咪的搜索数量更少
dfs(0,0);//考虑第i个猫，放入第j个车
cout<<ans<<endl;
return 0;
}
数独
题目链接：数独
分析：还是很有意思的一题的，以后不用自己写数独了 ，其实直接爆搜是很容易的，但我们肯定要考虑优化，不然铁定TLE，关于优化的各种细节都在代码中。
代码实现：
#include<iostream>
using namespace std;
const int N=9,M=1<<N;
char num[100];
int map[M];//map[i]的值就是以二为底i的对数
int cnt[M];//cnt[i]存储i的二进制表示中1的个数
int row[N],col[N],cell[3][3];//row,col,cell分别用一个二进制数表示一行、一列、一个九宫格的状态，二进制的第i位为1就代表i能选，假设从右往左分别是第1、2、3……位
void draw(int x,int y,int n,bool is_set){//is_set为true时把x，y对应位置的字符设为'1'+n，为false时把该位置该为'.'，并更新row，col，cell数组的状态
if(is_set) num[x*N+y]='1'+n;
else num[x*N+y]='.';
int v=1<<n;
if(!is_set) v=-v;//如果是改为.的话，那么状态应该加上v，因为这个位置的数又能选了
row[x]-=v;
col[y]-=v;
cell[x/3][y/3]-=v;//x/3和y/3分别对应九宫格的横坐标和纵坐标
}
void init(){
//初始时每个数都能用
for(int i=0;i<N;i++) row[i]=col[i]=(1<<N)-1;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
cell[i][j]=(1<<N)-1;
}
int lowbit(int x){//找到最低的一位1
return x&-x;
}
int get(int x,int y){
return row[x]&col[y]&cell[x/3][y/3];//返回三个数&之后的值，返回的数某一位为1，就说明这个数字可选
}
bool dfs(int c){
if(!c) return true;//搜到了答案
//找出可填数最少的位置
int minc=10;
int x,y;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
if(num[i*N+j]=='.'){
int tmp=get(i,j);
if(cnt[tmp]<minc){
minc=cnt[tmp];
x=i,y=j;
}
}
int tmp=get(x,y);
for(int i=tmp;i;i-=lowbit(i)){
int t=map[lowbit(i)];//找出能填几
draw(x,y,t,true);//填上
if(dfs(c-1)) return true;//这样能保证一旦搜到答案，就会逐层返回，结束dfs
draw(x,y,t,false);//去掉
}
return false;//未搜到答案
}
int main(){
for(int i=0;i<N;i++) map[1<<i]=i;
for(int i=0;i<1<<N;i++)
for(int j=0;j<N;j++)
cnt[i]+=i>>j&1;
while(cin>>num,num[0]!='e'){
init();
int s=0;//记录.的个数
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
if(num[i*N+j]=='.') s++;
else{
int t=num[i*N+j]-'1';//把字符1~9转化为数字0~8
draw(i,j,t,true);//调用draw函数
}
dfs(s);//搜索
puts(num);//输出num数组
}
return 0;
}
木棒
通过前面几道题的学习，我们发现搜索的剪枝与优化真不是一个很简单的问题，对于这一道问题同样如此。
题目链接：木棒
分析：爆搜很容易想到，我们直接考虑怎么剪枝，具体细节见代码。
代码实现：
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=64;
int n,w[N],sum,str,len;//sum表示总长度
bool st[N];//记录每个点是否枚举过了
//因为我们可能会出现既枚举1，3，2，又枚举1，2，3的情况，因此我们按顺序从前往后枚举保证只枚举组合数
bool dfs(int u,int len,int x){//考虑到第u组，当前长度为len，从第x个数开始枚举
if(u*str==sum) return true;//满足分完了
if(len==str) return dfs(u+1,0,0);//如果这一组枚举完成，就继续下面的枚举
for(int i=x;i<n;i++){
if(st[i]||w[i]+len>str) continue;//加入过了或者不能加入
st[i]=1;
if(dfs(u,w[i]+len,i+1)) return true;
st[i]=0;//恢复现场
if(!len||w[i]+len==str) return false;
/*
这里是说如果这个木棒是这一组的第一个或者最后一个木棒但却没有解决方案的情况
假设该分支后面还有合法方案，那么这个数会在后面的组中
如果该数在该组中第一个位置，那么后面只会枚举编号更大的数
如果把它放在后面的组，它肯定还是在第一个位置
(若有编号更小的数和此数组成合法方案的情况，前面就会枚举到)
但这个数放在第一个位置无解，因此这整个分支无解
是最后一个木棒的情况同理
主要用假设法，然后等效替换，推出矛盾
*/
//走到这里说明这个木棒不行
int j=i;//和i相同长度的木棒肯定也不行
while(j<n&&w[j]==w[i]) j++;
i=j-1;
}
return false;
}
int main(){
while(cin>>n,n){
memset(st,0,sizeof st);
str=len=sum=0;
for(int i=0;i<n;i++){
cin>>w[i];
sum+=w[i];
}
sort(w,w+n,greater<int>());//从最大的长度开始枚举，所枚举的状态更少
str=w[0];//从最大长度的开始
while(1){
//从小到大枚举str，一旦找到就break，一定得到的是最小的
if(sum%str==0&&dfs(0,0,0)) break;//必须满足str是len的约数才能分成若干组
str++;
}
cout<<str<<endl;
}
return 0;
}
生日蛋糕
题目链接：生日蛋糕
分析：很变态的一题。注意：题目答案并不具有单调性，因此不能二分。
感觉AcWing的某用户题解写的太好了，我就不献丑了。题解链接：生日蛋糕
代码实现：
#include<iostream>
#include<cmath>
using namespace std;
const int N=25,INF=1e9;
int minv[N],mins[N];//minv[i]表示前i层所需的最小体积
int n,m;
int res=INF;
int R[N],H[N];//记录每层的半径与高度
void dfs(int u,int s,int v){//u是当前层数，s是已用面积，v是已用体积
if(s+mins[u]>=res) return ;
if(v+minv[u]>n) return ;
if(s+2*(n-v)/R[u+1]>=res) return ;
if(!u){
if(v==n) res=s;
return ;
}
//搜索顺序，先R后H，从大到小
for(int r=min(R[u+1]-1,(int)sqrt((n-v-minv[u-1])/u));r>=u;r--)
for(int h=min(H[u+1]-1,(n-v-minv[u-1])/r/r);h>=u;h--){
H[u]=h,R[u]=r;
if(u==m) dfs(u-1,s+2*r*h+r*r,v+r*r*h);
else dfs(u-1,s+2*r*h,v+r*r*h);
//这里不用恢复现场，因为后面用不到这些H[u],R[u]了，再次用到它们的时候它们也是先被修改再被使用
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
minv[i]=minv[i-1]+i*i*i;
mins[i]=mins[i-1]+2*i*i;
}
R[m+1]=H[m+1]=INF;//减少边界判断
dfs(m,0,0);//从最低层开始搜
if(INF==res) res=0;
cout<<res<<endl;
return 0;
}
迭代加深
迭代加深是什么意思呢？在我们dfs得过程中，会有多个分支，有可能我们从某一个分支在很浅的层数就能搜到答案，而另一个分支却像无底洞一样深，其实就是我们不能大致判断搜索层数的深浅且深浅可能相差很多的一类情况，这时我们可以人为设计一个层数，从限制只能搜一层开始，逐渐放宽限制，直到搜到答案或无解结束，而一般来说前面几层的状态数相比最后一层算是比较少的，因此我们花费的时间也不会因此多出特别多，因此我们可以这样做以防我们搜到了一条很坑的路径但答案却在很短的另一条路径中。这种方法也常与我们下面要讲的IDA*算法相结合。
加成序列
题目链接：加成序列
分析：就按照上面的思路来写代码，其实和宽搜很不一样。
代码实现：
#include<iostream>
using namespace std;
const int N=110;
int path[N],n;
bool dfs(int u,int depth){
if(u==depth) return path[u-1]==n;//如果搜完了最后一层，判断结果是否正确并返回
bool st[N]={0};
for(int i=u-1;i>=0;i--)//从大到小枚举，情况数更少
for(int j=i;j>=0;j--){
int s=path[i]+path[j];
if(s>n||s<=path[u-1]||st[s]) continue;//如果s大于n或者s小于等于最后一个数或者s已经枚举过了（比如序列中有1，2，3，那么3就会被枚举2次），就continue
st[s]=1;
path[u]=s;//加入序列
if(dfs(u+1,depth)) return true;
//这里不用恢复现场，因为path[u]会被覆盖掉
}
return false;
}
int main(){
path[0]=1;//第一个数是1
while(cin>>n,n){
int depth=1;
while(!dfs(1,depth)) depth++;
for(int i=0;i<depth;i++) cout<<path[i]<<" ";
puts("");
}
return 0;
}
双向DFS
感觉这叫个双向DFS好奇怪，可能是y总自己起的？我们通过一道题来看。
送礼物
题目链接：送礼物
分析：嘿！这不是01背包吗？看一眼体积，打扰了。我们发现物品数比较少，因此可以考虑爆搜，直接爆搜好像会爆掉，因此我们考虑玄学 优化，我们可以把所有物品分成两组，第一组我们直接用爆搜求出所有能组成的重量小于等于W的重量，然后再枚举第二组的每一个数加入每一个组合中，这样会优化很多，当然，你也可以求导来推出两组物品分别有多少个的时候是最优的，而至于枚举重量，我们肯定是从大到小枚举更优，细节见代码。
代码实现：
要说双向BFS确实像双向，这个DFS？
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
int w,n,k;
const int N=50;
int ans;
//cnt从1开始，因为weight[0]=0也算一个方案，即什么也不搬
int a[N],weight[1<<25],cnt=1;//weight记录所有搜出来的体重，cnt记录数量，因为第一组最多有23个数，因此体重数最多有2的23次方种
void dfs1(int u,int s){//s记录当前的和
if(u==k){
weight[cnt++]=s;
return ;
}
dfs1(u+1,s);//不选这个数
if((LL)s+a[u]<=w) dfs1(u+1,s+a[u]);//选这个数
}
void dfs2(int u,int s){
if(u>=n){//如果考虑完了所有数，找到小于等于w的最大的数，并更新答案（if possible）
int l=0,r=cnt-1;
while(l<r){
int mid=l+r+1>>1;
if((LL)s+weight[mid]<=w) l=mid;
else r=mid-1;
}
ans=max(ans,s+weight[l]);
return ;
}
dfs2(u+1,s);//不选这个数
if((LL)s+a[u]<=w) dfs2(u+1,s+a[u]);//选这个数
}
int main(){
cin>>w>>n;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n,greater<int>());
k=n/2;//k代表第一组的数量
dfs1(0,0);//搜出第一组所有能组成的体重（小于等于W的），一共考虑0~k-1这k个数
sort(weight,weight+cnt);
cnt=unique(weight,weight+cnt)-weight;//排序并去重，用cnt记录去重后的数组大小
dfs2(k,0);//从第k个数开始考虑每个数
cout<<ans<<endl;
return 0;
}
IDA*
没错，又是那个玄学的算法，感觉这个就是A*算法的亲兄弟，它经常和迭代加深一起用，最难的还是相出求估计距离的方法。
排书
题目链接：排书
分析：这道题根据不同的情况会有差别很大的操作步数吧，因此我们考虑迭代加深，而这道题的情况太多了，我们可以枚举操作的长度，还可以枚举插入的位置，肯定TLE，我们考虑优化。我们发现，排好序后，每个数的后继（即它后面的数）都等于这个数+1，而我们的一次移动，最多只会改变三个数的后继（推荐自己手动操作一下），因此我们可以统计不满足正确后继的数的个数，把这个数除以3上取整得到的数当作最小步数，然后我们判断最小步数与当前步数之和是否大于最多步数，如果大于就直接砍掉这个分支，感觉策略很像A*算法，但是更像是一个剪枝的策略。果然搜索最难的还是剪枝。
代码实现：
#include<iostream>
#include<cstring>
using namespace std;
const int N=15;
int T,q[N],w[5][N],n;//w数组存储q的备份，因为可能同时多层，因此要开成二维的
int g(){//返回当前状态到终点的估计步数
int cnt=0;
for(int i=0;i<n-1;i++)
if(q[i]+1!=q[i+1])
cnt++;
return (cnt+2)/3;//返回cnt除以3上取整的值，最好不要写成(cnt-1)/3+1，因为这样的话即使cnt为0也会返回1，我以前就一直这么写但没错过，知道遇见了这道题。
}
bool check(){//检查当前状态是否合法
for(int i=0;i<n-1;i++)
if(q[i]+1!=q[i+1])
return false;
return true;
}
bool dfs(int u,int d){
if(u+g()>d) return false;
if(check()) return true;
for(int len=1;len<=n;len++)
for(int l=0;l+len-1<n;l++){
int r=l+len-1;
//因为将这组数往前面插等效于前面某组数往后插，而这种情况已经枚举过了
for(int k=r+1;k<n;k++){//枚举插入的位置，只往后面插
memcpy(w[u],q,sizeof q);//备份下，还原现场要用
int x,y;
//插入操作
for(x=r+1,y=l;x<=k;x++,y++)q[y]=w[u][x];
for(x=l;x<=r;x++,y++) q[y]=w[u][x];
if(dfs(u+1,d)) return true;
memcpy(q,w[u],sizeof q);//还原现场
}
}
return false;
}
int main(){
cin>>T;
while(T--){
cin>>n;
for(int i=0;i<n;i++) cin>>q[i];
int d=0;
while(d<5&&!dfs(0,d)) d++;//这里有可能一层不搜就是正确的，因此从第0层开始搜
if(d>=5) puts("5 or more");
else cout<<d<<endl;
}
return 0;
}
回转游戏
题目链接：回转游戏
分析：对于这题，我们怎么求最短操作数呢？我们发现，中间8个数里面最多的数对应操作步骤最少，假设最多的有cnt个，那么我们的最短操作数就是8-cnt了，因为一次操作会出去一个数并进来一个数，最优情况就是进去一个与最多的数不同的数，进来一个相同的数。可是这题写起来真的好繁琐啊，我们可以打表来简化操作，我们用一个二维数组存储每一种操作，使每一种操作对应的操作都相同，这样我们的代码就大大简化了。
代码实现：
#include<iostream>
using namespace std;
//打表真是一种技术啊！
const int op[8][7]={//记录每一种操作对应的数字坐标，来使每一种操作都变成把相邻两个坐标对应的数字交换（第一个和最后一个也算做相邻）
{0,2,6,11,15,20,22},
{1,3,8,12,17,21,23},
{10,9,8,7,6,5,4},
{19,18,17,16,15,14,13},
{23,21,17,12,8,3,1},
{22,20,15,11,6,2,0},
{13,14,15,16,17,18,19},
{4,5,6,7,8,9,10}
};
const int opposite[8]={5,4,7,6,1,0,3,2};//记录每一种操作的逆操作，如果我们上一次执行A，这一次就不枚举F了，因为再执行F的话相当于又回去了
const int center[8]={6,7,8,11,12,15,16,17};//记录目标的八个格子的数字坐标
const int N=24;
int q[N],path[100];//path存储的是操作方法，用0~7表示，输出时转化为A~H
int g(){//估值函数
int sum[4]={0};
for(int i=0;i<8;i++) sum[q[center[i]]]++;
int m=0;
for(int i=1;i<4;i++) m=max(m,sum[i]);
return 8-m;
}
void operate(int x){
int t=q[op[x][0]];
for(int i=0;i<6;i++) q[op[x][i]]=q[op[x][i+1]];
q[op[x][6]]=t;
}
bool dfs(int u,int d,int last){//我们记录last，即上一步的操作
if(u+g()>d) return false;
if(!g()) return true;
for(int i=0;i<8;i++){
if(opposite[i]==last) continue;
operate(i);
path[u]=i;
if(dfs(u+1,d,i)) return true;
operate(opposite[i]);//恢复现场
}
return false;
}
int main(){
while(cin>>q[0],q[0]){
for(int i=1;i<24;i++) cin>>q[i];
int d=0;
while(!dfs(0,d,-1)) d++;
if(!d) cout<<"No moves needed";
else
for(int i=0;i<d;i++)
cout<<char('A'+path[i]);//注意强转为char，不然会打印数字
cout<<endl<<q[6]<<endl;//第6个位置对应的就是8个的其中之一
}
return 0;
}
搜索终于结束了，其实搜索内容我们已经讲得差不多了，基本上就剩一个舞蹈链了，但这玩意比较难，放在后面单独讲。
扫一扫
279
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
