寒假训练搜索专题

题目链接：搜索

A 棋盘问题

题意很简单 就是k个棋子摆放在棋盘的方案，要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列。
经典dfs深搜题

#include 
#define ll long long
using namespace std;
const int maxn=1e5+100;
int n,k,ans,cnt;
int vis[20];
char a[20][20];
//搜索行数 vis数组记录列 
void dfs(int cur)
{	if(cnt==k){ans++;return ;}if(cur>=n) return ;for(int i=0;i<n;i++){if(!vis[i]&&a[cur][i]=='#'){vis[i]=1;//记录搜过的列 cnt++;dfs(cur+1);//搜索下一行 vis[i]=0;//回溯 cnt--;}}dfs(cur+1);
}
int main()
{while(~scanf("%d %d",&n,&k)){if(n==-1&&k==-1) break;ans=0; cnt=0;memset(vis,0,sizeof(vis));for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>a[i][j];}}dfs(0);printf("%d\n",ans);}return 0;
} 

B - Perket

你有 N 种配料，每种配料有酸度 S 和苦度 B 。用这些配料做成Perket时，总的酸度为所有配料酸度的乘积，总的苦度是所有配料苦度的和。你至少需要添加一种配料。
为了使口感适中，总的酸度和苦度之差的绝对值应该尽可能小，求这个最小值。
dfs深搜每次两种情况，选或不选，取所有情况中最小的。

#include 
#define ll long long
using namespace std;
const int maxn=1e5+100;
const int inf = 0x3f3f3f3f;
int n,s[20],b[20],mn;
void dfs(int h,int x,int y)
{if(h>=n){if(x==1&&y==0) return ;//只有1个不选 直接返回//cout<mn=min(mn,abs(x-y));return ;}dfs(h+1,x*s[h],y+b[h]);dfs(h+1,x,y);
}
int main()
{scanf("%d",&n);mn=inf;for(int i=0;i<n;i++) scanf("%d %d",&s[i],&b[i]);dfs(0,1,0);printf("%d\n",mn);return 0;
}

C - 全排列

这个题用c写的话比较麻烦，因为必须先进行字符串排序。c++写的话很方便 可以直接调用STL库里的全排列函数next_permutation。

#include 
#define ll long long
using namespace std;
const int maxn=1e5+100;
int main()
{string s;cin>>s;sort(s.begin(),s.end());//首先进行排序 因为要求所有情况从小到大输出do{cout<<s<<endl;}while(next_permutation(s.begin(),s.end()));return 0;
}

D - 自然数拆分
对于任意大于 11 的自然数 nn，总是可以拆分成若干个小于 nn 的自然数之和。

现请你编写程序求出 nn 的所有拆分。

#include 
#define ll long long
using namespace std;
const int maxn=1e5+100;
int n,k,t,top;// top记录拆分数的下标
int ans[30];
void dfs(int h)
{if(top==1&&n==0) return ;if(n==0){printf("%d=",t);for(int i=0;i<top-1;i++){printf("%d+",ans[i]);}printf("%d\n",ans[top-1]);return;}for(int i=h;i<=n;i++){ans[top++]=i;n-=i;dfs(i);top--;//回溯n+=i;}return ;
}
int main()
{scanf("%d",&t);n=t;dfs(1);//从1开始拆return 0;
} 

E - Prime Ring Problem

经典素数环问题，这个对格式卡的严，主要注意 每个样例之间有两次换行，最后一个样例有一个换行。

#include 
#define ll long long
using namespace std;
const int maxn=1e5+100;
int n,vis[30],ring[30];
int prime(int n)
{if(n<=1) return 0;for(int i=2;i<=sqrt(n);i++){if(n%i==0) return 0;}return 1;
}
void dfs(int cur)
{if(cur==n){if(prime(ring[0]+ring[n-1]))//判断素数环首尾数之和是否为素数，如果是，则找到解 {for(int i=0;i<n-1;i++){printf("%d ",ring[i]);}printf("%d\n",ring[n-1]);}return ;}for(int i=2;i<=n;i++){if(!vis[i]&&prime(i+ring[cur-1]))//当i未被使用且i与环中最后一个数之和为素数时，将其填入素数环 {vis[i]=1;//记录用过的数ring[cur]=i;dfs(cur+1);vis[i]=0;//回溯}}
}
int main()
{int t=0;while(~scanf("%d",&n)){if(t) printf("\n");t++;memset(vis,0,sizeof(vis));ring[0]=1;//先将1填入，作为素数环的起点printf("Case %d:\n",t);dfs(1);//从环的第2个数开始搜素}return 0;
}

F - Red and Black

有一个长方形的房间，覆盖了正方形的磁砖。每块磁砖的颜色，要么是红色，要么是黑色。一名男子站在一块黑色的磁砖上。他可以从一块磁砖移至相邻四块磁砖中的某一块。但是，他不允许在红色磁砖上移动，他只允许在黑色磁砖上移动。
编写一个程序，使得他允许重复上述的移动，判断他所能到达的黑色磁砖的数量。

#include 
#define ll long long
using namespace std;
const int maxn=1e5+100;
int vis[30][30],n,w,h,ans;
char a[30][30];
int dx[5]={0,1,0,-1};
int dy[5]={1,0,-1,0};
void dfs(int x,int y)
{vis[x][y]=1;//标记搜索过的ans++;for(int i=0;i<4;i++){int x1=x+dx[i];int y1=y+dy[i];if(x1>=0&&x1<h&&y1>=0&&y1<w&&a[x1][y1]!='#'&&!vis[x1][y1])//判断是否符合要求{dfs(x1,y1);}}
}
int main()
{while(~scanf("%d %d",&w,&h)){if(w==0&&h==0) break;ans=0;memset(vis,0,sizeof(vis));for(int i=0;i<h;i++){for(int j=0;j<w;j++){cin>>a[i][j];}}int x,y;for(int i=0;i<h;i++){for(int j=0;j<w;j++){if(a[i][j]=='@'){x=i; y=j;//记录起始点} //printf("%c",a[i][j]);}//printf("\n");}dfs(x,y);printf("%d\n",ans);}return 0;
} 

G - Knight Moves

编写一个程序，计算一个骑士从棋盘上的一个格子到另一个格子所需的最小步数。 骑士的走法就是象棋中马的走法，有8个方向。
求最小步数一看就知道是bfs。

#include 
#include 
#include 
#include 
#include 
#define ll long long
using namespace std;
const int maxn=1e5+100;
int vis[330][330],n,m,t;
char a[330][330];
int dir[8][2]={{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};//8个方向
struct node
{int x,y,d;//x,y为坐标 d为所用的步数node(int xx,int yy,int dd){//便于输入结构体里面的值x=xx;y=yy;d=dd;}
};
void bfs(int sx,int sy,int ex,int ey)
{queue<node>q;//创建队列方便操作q.push(node(sx,sy,0));vis[sx][sy]=1;while(!q.empty()){node now=q.front();//队列第一个q.pop();//删除队列第一个if(now.x==ex&&now.y==ey){//找到终点printf("%d\n",now.d);break;}for(int i=0;i<8;i++){int tx=now.x+dir[i][0];int ty=now.y+dir[i][1];if(tx>=0&&tx<n&&ty>=0&&ty<n&&!vis[tx][ty]){vis[tx][ty]=1;q.push(node(tx,ty,now.d+1));}}}
} 
int main()
{scanf("%d",&t);int sx,sy,ex,ey;while(t--){scanf("%d",&n);memset(vis,0,sizeof(vis));scanf("%d %d %d %d",&sx,&sy,&ex,&ey);bfs(sx,sy,ex,ey);}return 0;
}

H - Oil Deposits

某公司负责探测地下油层，每次处理一个大的矩形区域。先创建一个网格，将土地划分为许多方形块，然后用传感设备分别探测每个地块，以确定该地块是否含有石油。一块含有石油的土地叫做pocket。如果两个pocket边相邻或对角相邻，则它们属于同一油层的一部分。你的工作是确定在一个网格有多少不同的油层。
这个类型也是经典的深搜题。

#include 
#define ll long long
using namespace std;
const int maxn=1e5+100;
int n,m,vis[110][110];
char a[110][110];
int dir[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
void dfs(int x,int y)
{vis[x][y]=1;//标记搜过的油田for(int i=0;i<8;i++){int tx=x+dir[i][0];int ty=y+dir[i][1];if(tx>=0&&tx<n&&ty>=0&&ty<m&&!vis[tx][ty]&&a[tx][ty]=='@'){dfs(tx,ty);}}
}
int main()
{while(~scanf("%d %d",&n,&m)){if(n==0&&m==0) break;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>a[i][j];}}int ans=0;memset(vis,0,sizeof(vis));for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(a[i][j]=='@'&&!vis[i][j]){//找到未曾记录的油田就搜索ans++;dfs(i,j);}}}printf("%d\n",ans);}return 0;
}

I - Lake Counting

这个题跟H题一个意思

#include 
#define ll long long
using namespace std;
const int maxn=1e5+100;
int n,m,vis[110][110];
char a[110][110];
int dir[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};//8个方向
void dfs(int x,int y)
{vis[x][y]=1;for(int i=0;i<8;i++){int tx=x+dir[i][0];int ty=y+dir[i][1];if(tx>=0&&tx<n&&ty>=0&&ty<m&&!vis[tx][ty]&&a[tx][ty]=='W'){dfs(tx,ty);}}
}
int main()
{scanf("%d %d",&n,&m);for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>a[i][j];}}int ans=0;memset(vis,0,sizeof(vis));//每次初始化标记数组for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(a[i][j]=='W'&&!vis[i][j]){ans++;dfs(i,j);}}}printf("%d\n",ans);return 0;
}

J - 二叉树先序遍历

输入一个整数n（n <= 100000），表示二叉树中节点个数，编号为1~n。约定1号节点为二叉树的根节点。然后输入n行，每行包括两个整数，第i行表示编号为i的节点的左子节点和右子节点的编号。如果某个节点没有左子节点，那么对应输行的第一个整数为0；如果某个节点没有右子节点，那么对应行的第二个整数为0。
先序遍历输出此二叉树每个节点的编号，每行输出一个编号
前序遍历首先访问根节点然后遍历左子树，最后遍历右子树。

#include 
#define ll long long
using namespace std;
const int maxn=1e5+100;
struct node//结构体构造树
{int l;int r;
}p[maxn];
void dfs(int x)
{if(x==0) return ;printf("%d\n",x);//输出根dfs(p[x].l);//遍历左子树dfs(p[x].r);//遍历右子树
}
int main()
{int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d %d",&p[i].l,&p[i].r);}dfs(1);//从根节点开始遍历return 0;
}

K - 迷宫（一）

一天蒜头君掉进了一个迷宫里面，蒜头君想逃出去，可怜的蒜头君连迷宫是否有能逃出去的路都不知道。

看在蒜头君这么可怜的份上，就请聪明的你告诉蒜头君是否有可以逃出去的路。深搜dfs

#include 
#define ll long long
using namespace std;
const int maxn=1e5+100;
int vis[30][30];
char a[30][30];
int n,m,sx,sy,ex,ey,flag; 
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};//4个方向
void dfs(int x,int y)
{if(x==ex&&y==ey){flag=1;return ;}else{for(int i=0;i<4;i++){int nx=x+dir[i][0];int ny=y+dir[i][1];if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!vis[nx][ny]&&a[nx][ny]!='*'){vis[nx][ny]=1;dfs(nx,ny);vis[nx][ny]=0;//回溯}}}
}
int main()
{scanf("%d %d",&n,&m);memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];if(a[i][j]=='S'){sx=i;sy=j;//记录起点}if(a[i][j]=='T'){ex=i;ey=j;//记录终点} }}dfs(sx,sy);if(flag) printf("yes\n");else printf("no\n");return 0;
}

L - 马走日

这个题跟J题比较像，不过这个题要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。就是遍历点的数目达到n*m。

#include 
#define ll long long
using namespace std;
const int maxn=1e5+100;
int vis[330][330],n,m,t,k,ans;
char a[330][330];
int dir[8][2]={{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};//8个方向
void dfs(int x,int y,int d)
{if(d==k){ans++;return ;}for(int i=0;i<8;i++){int tx=x+dir[i][0];int ty=y+dir[i][1];if(tx>=0&&tx<n&&ty>=0&&ty<m&&!vis[tx][ty]){vis[tx][ty]=1;dfs(tx,ty,d+1);vis[tx][ty]=0;}}
} 
int main()
{int t;scanf("%d",&t);while(t--){int sx,sy;ans=0;memset(vis,0,sizeof(vis));scanf("%d %d %d %d",&n,&m,&sx,&sy);k=n*m;//所有点的个数vis[sx][sy]=1;//起点首先标记dfs(sx,sy,1);printf("%d\n",ans);} return 0;
}

M - 八皇后问题

努比亚和苏丹没有子女，所以他要从一些有集成资格的继承者中挑选一个出来继承王位。他希望这个继承者足够聪明，所以他准备了一个西洋棋盘，上面的每个格子中均有一个 1-99 的数字。他又准备了 8 个皇后棋子。
8 皇后的规则就是不能有任何棋子同行或者同列或者同斜线，在满足这个规则的同时，王位继承者还需要让 88 个皇后所在的位置的数字的和是最大的。
八皇后属于经典dfs问题，输出和最大，在搜索过程中弄一个变量记录和。

#include 
#define ll long long
using namespace std;
const int maxn=1e5+100;
int n,ans,mp[30];
int vis[3][30],a[30][30];
void dfs(int cur,int s)
{int i;if(cur==8){//输出n个皇后所在列的列号 /*for(i=0;ians=max(ans,s);//记录最大的//ans++;return;}for(i=0;i<8;i++){//该列没有放过棋子 且 主对角线没有放过棋子 且 副对角线没有放过棋子 if(!vis[0][i] && !vis[1][cur+i] && !vis[2][cur-i+n]){vis[0][i]=1;vis[1][cur+i]=1;vis[2][cur-i+n]=1;mp[cur]=i+1;dfs(cur+1,s+a[cur][i]);vis[0][i]=0;vis[1][cur+i]=0;vis[2][cur-i+n]=0;}}
}
int main()
{scanf("%d",&n);while(n--){ans=0;memset(mp,0,sizeof(mp));memset(vis,0,sizeof(vis));for(int i=0;i<8;i++)for(int j=0;j<8;j++)scanf("%d",&a[i][j]);dfs(0,0);printf("%d\n",ans);} return 0;
}

N - 选数

已知 n个整数 x1,x2,…xn，以及一个整数 k（k

#include 
#define ll long long
using namespace std;
const int maxn=1e5+100;
int a[maxn];
int n,k,ans;
bool prime(int x)//判断是否为素数
{for(int i=2;i<=sqrt(x);i++){if(x%i==0)return false;}return true;
}
void dfs(int t,int sum,int d)
{if(t==k){if(prime(sum))ans++;return ;}else{for(int i=d;i<n;i++){dfs(t+1,sum+a[i],i+1);}}
}
int main()
{scanf("%d%d",&n,&k);for(int i=0;i<n;i++) scanf("%d",&a[i]);dfs(0,0,0);printf("%d\n",ans);return 0;
}

O - 打开灯泡 Switch the Lamp On

给出n行m列的斜线，要求从(0，0)走到(n，m)，只能往四个斜方向走，若斜线方向与走的方向相同，花费为0，否则花费为1.
思路：
bfs求花费最小的路，不过这题要用双端队列，用双端队列是为了维护队列中的单调性，即队列中元素的step一定时从队首到队尾单调递增的(并不严格递增)。就是每次搜索到花费为0的路放队首，为1的路放队尾，还有一些细节就是用数组book[i][j]，记录搜索时i，j之间的最小花费，搜索时不是看是否搜索过，而是比较是否比最小花费小。

#include 
#define ll long long
#define inf 0x7ffffff
using namespace std;
const int maxn=1e5+100;
int n,m,flag;
char map1[600][600];
struct node 
{int x,y,step;
} wer;
int book[600][600];
deque<node>q;
int nxtx[10]= {0,-1,1,-1,1};
int nxty[10]= {0,-1,-1,1,1};
int cost(int x,int y,int s) 
{ if(s==1&&map1[x-1][y-1]=='\\')  return 0;//'\\'代表字符'\'if(s==2&&map1[x][y-1]=='/')  return 0;if(s==3&&map1[x-1][y]=='/') return 0;if(s==4&&map1[x][y]=='\\') return 0;return 1;
}
void bfs() 
{node t;t.x=1;t.y=1;t.step=0;q.push_back(t);while(!q.empty()) {node tmp=q.front();q.pop_front();for(int i=1; i<=4; i++) {int x=tmp.x,y=tmp.y,step=tmp.step;int nx=x+nxtx[i];int ny=y+nxty[i];step=step+cost(x,y,i);if(nx>=1&&ny>=1&&nx<=n+1&&ny<=m+1&&book[nx][ny]>step) {book[nx][ny]=step;node tmp1;//扩展点tmp1.x=nx;tmp1.y=ny;tmp1.step=step;if(cost(x,y,i)) { q.push_back(tmp1);} else {q.push_front(tmp1);}if(nx==n+1&&ny==m+1) {flag=1;break;}}}if(flag) {break;}}if(flag==0) printf("NO SOLUTION\n");
}
int main() 
{scanf("%d%d",&n,&m);for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {cin >> map1[i][j];}}for(int i=1; i<=n+1; i++) { for(int j=1; j<=m+1; j++) {book[i][j]=inf;}}bfs();if(flag) printf("%d\n",book[n+1][m+1]);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！