首页 > 其他分享 >搜索

搜索

时间：2023-10-16 18:23:49浏览次数：24  
标签：std int dfs 搜索 && using include

搜索专题

目录

P1219 八皇后 Checker Challenge（深搜）

  • 思路：深搜当先行的每一个点，如果满足，就在该点处放置然后进入下一层深搜。终止条件是搜完最后一行。
  • 注意点1：存的时候按行、列、左对角线、右对角线存，存该直线上是否有棋子；
  • 注意点2：右对角线规律是相减为固定值，但是相减可能为负数，所以+n全部变为正再存
#include<bits/stdc++.h>
using namespace std;
int n,ct;
int row[100],col[100],ldia[100],rdia[100];
void print()
{
	if(ct<3)
	{
		for(int i=1;i<n;i++)
		{
			cout<<row[i]<<" ";
		}
		cout<<row[n]<<endl;
	}
	ct++;
}
void dfs(int k) //k表示当前行 
{
	if(k>n)
	{
		print();
		return;
	}
	for(int i=1;i<=n;i++) //遍历每一列 
	{
		if(!col[i]&&!ldia[k+i]&&!rdia[k-i+n])
		{
			row[k]=i;
			col[i]=1;
			ldia[k+i]=1;
			rdia[k-i+n]=1;
			dfs(k+1);
			row[k]=0;
			col[i]=0;
			ldia[k+i]=0;
			rdia[k-i+n]=0;
		}
	}
 } 
int main()
{
	cin>>n;
	dfs(1);
	cout<<ct<<'\n';
	return 0;
 }

P2392 kkksc03考前临时抱佛脚（还可用动规）

  • 思路1（WA）：贪心，当前哪边脑子用时少就把这道题加在哪边。

  • 错因：还要想办法让左右脑的差距最小

    #include<bits/stdc++.h>
using namespace std;
int ans;
int s[10]; 
int main()
{
	for(int i=1;i<=4;i++)
	cin>>s[i];
	
	for(int i=1;i<=4;i++)
	{
		int l=0,r=0,x;
		for(int j=1;j<=s[i];j++)
		{
			cin>>x;
			if(r<=l)
			r+=x;
			else
			l+=x;
		}
		ans+=max(l,r);
	}
	
	cout<<ans;
	
	return 0;
}

  • 思路2：暴搜

    #include<bits/stdc++.h>
using namespace std;
int ans,minn,l,r;
int s[10],ts[10][100]; 

void search(int i,int k) //第i门课的第k个作业 
{
	if(k>s[i])
	{
		minn=min(minn,max(l,r));
		return ;
	}
	l+=ts[i][k];
	search(i,k+1);
	l-=ts[i][k];
	r+=ts[i][k];
	search(i,k+1); 
	r-=ts[i][k];
}
int main()
{
	for(int i=1;i<=4;i++)
	cin>>s[i];
	
	for(int i=1;i<=4;i++)
	{
		l=0,r=0;
		minn=5000;
		for(int j=1;j<=s[i];j++)
		{
			cin>>ts[i][j];
		}
		search(i,1);
		ans+=minn;
	}
	
	cout<<ans;
	return 0;
 }

P1135 奇怪的电梯（bfs）

  • 注意！！！广搜细节！！！

    #include<bits/stdc++.h>
using namespace std;
const int N=1000;
int n,a,b,step;
int k[N],vis[N];

int main()
{
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++)
	cin>>k[i];
	bool f=0;
	queue<int> q;
	q.push(a);
	vis[a]=1;
	while(!q.empty())
	{
		int kk=q.size();  //这里！！！一定要把size先存一下！！！不然q.size()就是变化的！！！！！
		for(int i=0;i<kk;i++)
		{
			int x=q.front();
			q.pop();
			if(x==b)
			{
				f=1;
				break;
			}
			if(x-k[x]>=1&&!vis[x-k[x]])
			{
				vis[x-k[x]]=1;
				q.push(x-k[x]);
			}
			if(x+k[x]<=n&&!vis[x+k[x]])
			{
				vis[x+k[x]]=1;
				q.push(x+k[x]);
			}
		}
		if(f)
		break;
		step++;
	}
	if(!f)
	{
		cout<<-1<<'\n';
	}
	else
	cout<<step<<'\n';

	return 0;
}

P2895 Meteor Shower S（二维bfs）

  • 记录每一个格子被流行砸的时间是哪一个时刻，在该时刻前贝西就能走。

  • 二维：用两个队列分别存x和y

    #include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int m,x,y,t,step;
bool f=0;
int timel[310][310],vis[310][310]; 
int xx[6]={0,0,0,1,-1};
int yy[6]={0,1,-1,0,0};
int main()
{
	for(int i=0;i<310;i++)
	{
		for(int j=0;j<310;j++)
		timel[i][j]=-1;
	}
	
	cin>>m;
	while(m--)
	{
		cin>>x>>y>>t;
		for(int i=0;i<5;i++)
		{
			if((x+xx[i]>=0&&y+yy[i]>=0)&&(t<timel[x+xx[i]][y+yy[i]]||timel[x+xx[i]][y+yy[i]]==-1))
			{
				timel[x+xx[i]][y+yy[i]]=t;
			}
		}
	}
	
	queue<int> q[2]; 
	q[0].push(0);
	q[1].push(0);
	vis[0][0]=1;
	while(!q[0].empty()&&!q[1].empty())
	{
		int sz=q[0].size();
		for(int i=0;i<sz;i++)
		{
			int nxx=q[0].front(),nyy=q[1].front();
			q[0].pop();
			q[1].pop();
			if(timel[nxx][nyy]==-1)
			{
				f=1;
				break;
			}
			for(int i=1;i<5;i++)
			{
				int nx=nxx+xx[i];
				int ny=nyy+yy[i];
				if(nx>=0&&ny>=0&&(step<timel[nx][ny]-1||timel[nx][ny]==-1)&&!vis[nx][ny])
			{
				vis[nx][ny]=1;
				q[0].push(nx);
				q[1].push(ny);
			}
			}			
		}
		if(f)
		break;
		step++;
	}
	if(f)
	cout<<step;
	else
	cout<<"-1"; 
	
	return 0;
 }

P1036 选数(深搜)

  • 思路：

  • 疑问：如果数据是5 3 3 7 12 19 19，输入是3，是3 7 19，3 7 19，3 19 19，但是3 7 19会被算两次？

    #include<bits/stdc++.h>
using namespace std;
int ans,n,k;
int a[100];
bool isprime(int x)
{
	if(x==0||x==1) return false;
	if(x==2) return true;
	for(int i=2;i<sqrt(x);i++)
	{
		if(x%i==0)
		return false;
	}
	return true;
}
//b是当前选了几个数 
//c是现在和为几 
//d表示当前加的从哪个数开始
void dfs(int b,int c,int d)
{
	if(b==k)
	{
		if(isprime(c))
		{
			ans++;
		}
		return ;
	}
	
	for(int i=d;i<n;i++)
	{
		dfs(b+1,c+a[i],i+1);
	}
	
	return;
}

int main()
{
	cin>>n>>k;
	
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	
//	sort(a,a+n);
	
	dfs(0,0,0);
	
	cout<<ans<<endl;
	
	return 0;
}

P1433 吃奶酪（还需用状态压缩优化）

  • 这里只用了dfs+剪枝

    #include<bits/stdc++.h>
using namespace std;
int n;
double ans=0x7fffffff;
double x[50],y[50],vis[50],dis[100][100];
void dfs(int now,double js,double sum)
{
	if(sum>ans)
	return ;//剪枝 
	if(js==n)
	{
		ans=min(ans,sum);
		return;
	}
	
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			vis[i]=1;
			//sum+=dis[now][i];注意这个地方不能这么写，不然for循环后面sum的值就加多了。如果要这么写，下面写回溯就要加一个sum-=dis[now][i]
			dfs(i,js+1,sum+dis[now][i]);
			vis[i]=0;
		}
	}
	return;
}

int main()
{
	cin>>n;
	x[0]=0;
	y[0]=0;
	for(int i=1;i<=n;i++)
	{
		cin>>x[i]>>y[i];
	}
	
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=n;j++)
		{
			 dis[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
		}
	}
	
	dfs(0,0,0);
	
	printf("%.2f",ans);
	return 0;
}

P1019 [NOIP2000 提高组] 单词接龙

  • 注意点1：开头的字母已经定了，所以“龙”只能往后接，不用考虑接到前面的问题。

  • 注意点2：要使“龙”最长，应取最小重叠部分

    #include<bits/stdc++.h>
using namespace std;
string s[50];
int n,ans;
int vis[50];
int canlink(string s1,string s2)
{
	int len1=s1.length();
	int len2=s2.length();
	int sum=0;
	for(int i=1;i<min(len1,len2);i++)
	{
		bool f=1;
		for(int j=0;j<i;j++)
		{
			if(s1[len1-i+j]!=s2[j])
			f=0;
		}
		if(f)
		return i;
	}
	
	return 0;
}

void dfs(string snow,int lnow) //当前的字符串，当前的长度
{	
	ans=max(lnow,ans);
	for(int i=0;i<n;i++)
	{
		if(vis[i]<2&&canlink(snow,s[i]))
		{
			vis[i]++;
			dfs(s[i],lnow+s[i].length()-canlink(snow,s[i]));//youwenti
			vis[i]--;
		}
	}
	
}
int main()
{
	cin>>n;
	for(int i=0;i<=n;i++)
	cin>>s[i];
	for(int i=0;i<n;i++)
	{
		if(s[i][0]==s[n][0]&&vis[i]<2)
		{
			vis[i]++;
			dfs(s[i],s[i].length());
			vis[i]--;
		}

	}
	cout<<ans;
	return 0;
 }

P1101 单词方阵（dfs）

  • 思路：找到y就从各个方向进dfs往下搜，只要有一个不对就return false。
#include<bits/stdc++.h>
using namespace std;
int n;
int vis[150][150];
string s[150];
string es="yizhong";
int xx[10]={1,1,0,-1,-1,-1,0,1};
int yy[10]={0,1,1,1,0,-1,-1,-1};

bool dfs(int x,int y,int de,int js)
{
	js++;
	if(js==7)
	return true;
	int nx=x+xx[de];
	int ny=y+yy[de];
	if(nx>=0&&nx<n&&ny>=0&&ny<n&&s[nx][ny]==es[js])
	{
		if(dfs(nx,ny,de,js))
		{
			vis[nx][ny]=1;
			return true;
		}
		else
		return false;
	}
	else
	return false;
}

int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	cin>>s[i];
	
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(s[i][j]==es[0])
			for(int k=0;k<8;k++)
			{
				if(dfs(i,j,k,0))
				{
					vis[i][j]=1;
				}
			}
		}
	
	}
	
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(vis[i][j])
			cout<<s[i][j];
			else
			cout<<"*";
		}
		cout<<endl;
	}
	
	return 0;
 }

P2404 自然数的拆分问题

  • 要用数组存一下每种情况，每次搜到底输出

    #include<bits/stdc++.h>
using namespace std;
int n,ans;
int a[15];
void dfs(int now,int sum,int js)
{
	if(sum>n)
	return ;
	if(sum==n)
	{
		ans++;
		for(int i=0;i<js-1;i++)
		{
			cout<<a[i]<<"+";
		}
		cout<<a[js-1]<<endl;
		return ;
	}
	
	for(int i=now;i<=n-1;i++)
	{
		a[js]=i;
		dfs(i,sum+i,js+1);
		a[js]=0;
	}
	return;
}

int main()
{
	cin>>n;
	dfs(1,0,0);

	return 0;
}

P1596 Lake Counting S（dfs）（染色）

  • 经典的数水洼问题
#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
char mp[110][110];
int xx[10]={1,1,1,0,0,-1,-1,-1};
int yy[10]={1,-1,0,1,-1,0,1,-1};
void dfs(int x,int y)
{
	for(int i=0;i<8;i++)
	{
		int nx=x+xx[i];
		int ny=y+yy[i];
		
		if(nx>=0&&nx<n&&ny>=0&&ny<m&&mp[nx][ny]=='W')
		{
			mp[nx][ny]='.';
			dfs(nx,ny);
		}
		
	}
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cin>>mp[i][j];
		}
	}
	
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(mp[i][j]=='W')
			{
				dfs(i,j);
				ans++;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

P1162 填涂颜色（染色）

  • 如果被1包围，则0一定挨不到边界，所以->把挨不到边界的0变成2 -> 把挨得到边界的0变成3，和被包围的0区分开
#include<bits/stdc++.h>
using namespace std;
int n;
int mp[50][50];
int xx[5]={1,-1,0,0};
int yy[5]={0,0,1,-1};
void dfs(int x,int y)
{
	for(int i=0;i<4;i++)
	{
		int nx=x+xx[i];
		int ny=y+yy[i];
		if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&mp[nx][ny]==0)
		{
			mp[nx][ny]=3;
			dfs(nx,ny);
		}
	}
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>mp[i][j];
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		if(mp[i][1]==0)
		{
			dfs(i,1);
		}
		if(mp[n][i]==0)
		{
			dfs(n,i);
		}
		if(mp[i][n]==0)
		{
			dfs(i,n);
		}
		if(mp[1][i]==0)
		{
			dfs(1,i);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(mp[i][j]==3)
			{
				cout<<0<<" ";
			}
			else if(mp[i][j]==0)
			cout<<"2 ";
			else
			cout<<mp[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

P1825 Corn Maze S（bfs）

  • 最短路径问题：应该用广搜。最开始用深搜超时了。
#include<iostream>
#include<queue>
using namespace std;
const int N=350;

struct point{
    int x;
    int y;
    int t;
};

queue<point> que;

char a[N][N];
bool vis[N][N];
int n,m;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int sx;
int sy;

void goto_another(int &nx,int &ny,int k)//goto_another函数用于寻找另一个传送门，nx、ny代表当前点的坐标，记得要加上取地址符'&'，因为每当贝西踏入一个传送门，它就会立即被传送至另一个传送门，不能在原地停留
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]==a[nx][ny]&&(i!=nx||j!=ny))//如果a[i][j]这个点的是一个与a[nx][ny]相同的传送门，并且a[i][j]与a[nx][ny]不是同一个点
            {
                nx=i;//改变当前坐标，将贝西强行移动至另一个传送门处
                ny=j;
                return ;//告辞
            }
        }
    }
}
int main()
{
    
    cin>>n>>m;
    string s;
    for(int i=1;i<=n;i++)
    {
        cin>>s;//由于输入奇奇怪怪地没有空格，于是乎窝便使用字符串读入
        for(int j=1;j<=m;j++)
        {
            a[i][j]=s[j-1];
            if(a[i][j]=='@')//获取起点坐标
            {
                sx=i;
                sy=j;
            }
        }
    }
    que.push((point){sx,sy,0});

    while(!que.empty())
    {
        point f=que.front();
        que.pop();
        if(a[f.x][f.y]=='=')
        {
            cout<<f.t;
            return 0;
        }
        if(a[f.x][f.y]>='A'&&a[f.x][f.y]<='Z')//特判部分，如果当前点是一个传送门，那么就传送至另一个传送门
        {
            goto_another(f.x,f.y,f.t);
        }
        for(int i=0;i<=3;i++)
        {
            int nx=f.x+dx[i];
            int ny=f.y+dy[i];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]!='#'&&!vis[nx][ny])
            {
                vis[nx][ny]=true;
                que.push((point){nx,ny,f.t+1});
            }
        }
    }
    return 0;
}

标签：std,int,dfs,搜索,&&,using,include
From： https://www.cnblogs.com/xiaoyangii/p/17768036.html

相关文章

  • Elasticsearch——terms聚合实现搜索热词统计
     最近项目中遇到一个需求。需要实现热词功能，需要给用户展示检索频率最高的10个关键字；由于项目中使用到了es，所以就使用es实现，具体实现如下：前提，拥有es环境；1、创建索引：POSThttp://localhost:9200/hotwords_test/_mapping{"properties":{"search_txt":{......
  • 折半(二分)查找算法—高效搜索算法
    折半查找算法（BinarySearchAlgorithm）是一种高效的搜索算法，常用于已排序的数组或列表中进行查找操作。它的核心思想是通过比较中间元素与目标值的大小关系来确定目标值在数组的哪一部分，从而缩小搜索范围。本文将详细介绍折半查找算法的原理、实现以及应用场景。一、原理折半查找算......
  • 算法修养--广度优先搜索BFS
    广度优先算法（BFS）广度优先算法（Breadth-FirstSearch）是在图和树领域的搜索方法，其核心思想是从一个起始点开始，访问其所有的临近节点，然后再按照相同的方式访问这些临近节点的节点，这种访问方式类似涟漪泛起，一层一层的扩散。广度优先算法解决的问题：从A点出发，有没有一条路径可以到达B......
  • 搜索与图论2.2-Floyd算法
    一、简述\(Floyd\)算法是一种可以快速求解图上所有顶点之间最短路径的算法。\(Bellman-Ford\)和\(Dijkstra\)算法求解的都是从一个起始点开始的最短路。如果想要求解图中所有顶点之间的最短路，就需要枚举每个点做为起点，这样十分低效。\(Floyd\)算法(也称\(Floyd-Warshall\)......
  • vscode中文搜索乱码或搜索不到
    使用vscode在全局搜索时，代码中的内容无法搜索出来，或者搜索出来是乱码。经验证：与vscode的语言设置无关，设置为中文或英文都是一样的后面猜想到会不会与文件自身的编码有关，因为我们项目中的代码文件大多是GB18030的，而vscode默认的编码应该是UTF-8解决方案经过验证有两2种方法可......
  • 算法0506 对数器 二分搜索
    对数器非常重要的自我验证代码正确性的方法在面试时或机试时写算法题，没有测试用例或者测试用例太少，导致巨大的数据量无法进行测试时。需要自己写测试用例数据时可以使用对数器。......
  • Linux 在多个文件中搜索关键字
    摘要：使用grep或者rg在当前目录下所有文件中查找关键字。  在Linux操作系统下，搜索文件中的关键字可帮助用户快速找到所需的信息，满足快速排查问题的需求。在大型系统中，文件可能被保存在多个目录中并且命名也可能不同，所以，逐个文件搜索就不现实了。小编在《Linuxgrep查询关键词首......
  • 1688关键字技术贴：提升搜索排名和转化率的实战指南
    1688，作为中国领先的B2B电子商务平台，为全球的买家和卖家提供了丰富的商品和服务。在这个巨大的市场环境中，如何让你的商品或服务脱颖而出，关键字的选择和优化是至关重要的。本文将分享一些1688关键字的技术贴，帮助你提升搜索排名和转化率。二、关键字的选择精准匹配：选择与你的商品或服......
  • 【开源三方库】Fuse.js：强大、轻巧、零依赖的模糊搜索库
     开源项目 OpenHarmony是每个人的 OpenHarmony曹天恒公司：中国科学院软件研究所小组：知识体系工作组 1.简介Fuse.js是一款功能强大且轻量级的JavaScript模糊搜索库，支持OpenAtom OpenHarmony（以下简称“OpenHarmony”）操作系统，它具备模糊搜索和排序等功能。该库高性能......
  • JAVA图搜索算法之DFS-BFS
    图算法DFS与BFSBFS和DFS代表对图进行遍历，即搜索的算法，搜索算法中常用的只要有两种算法:深度优先遍历(Depth-First-Search:DFS)和广度优先遍历(Breadth-First-Search:BFS)。一个图结构可以用来表示大量现实生活中的问题，比如，道路网络，计算机网络，社交网络，用户身份解析图①DFS......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99