算法竞赛_算法竞赛博客

今天带来的是广度优先搜索BFS
应用有：连通性，最短路等。

首先是算法思想：简单的说，每个时刻（阶段）要做的事就是从上个时刻（阶段）每个状态扩展出来的新状态。使用队列来实现，先将初始状态加入到空的队列中去，然后每次取出队头，找出队头元素能转移到的状态，将其压入队列；如此循环直到队列为空。这样就能保证一个状态在被访问的时候是最短路径了。

代码模板：

Q.push(初始状态);
while(!Q.empty()){
   State u=Q.front(); //取出队头元素
   Q.pop();
   for(枚举所有可扩展的状态) //找出u的可扩展状态
      if(状态合法)
       Q.push(v)  //入队
}
1
2
3
4
5
6
7
8

接着，更新洛谷p1443的题解

#include<bits/stdc++.h>
using namespace std;
const int maxn=500;
struct coord{
	int x,y;
};
int walk[8][2]={{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};
int n,m,sx,sy;
int ans[maxn][maxn];
int main(){
	queue<coord> Q;
	memset(ans,-1,sizeof(ans));
	cin>>n>>m>>sx>>sy;
	coord tmp={sx,sy};
	Q.push(tmp);
	ans[sx][sy]=0;
	while(!Q.empty()){
		coord u=Q.front();
		int ux=u.x,uy=u.y;
		Q.pop();
		for(int k=0;k<8;k++){
			  int x=ux+walk[k][0],y=uy+walk[k][1];
			  int d=ans[ux][uy];
			  if(x<1||x>n||y<1||y>m||ans[x][y]!=-1)
			    continue;
			  ans[x][y]=d+1;
			  coord tmp={x,y};
			  Q.push(tmp); 
		}
	}
	for(int i=1;i<=n;i++,puts(" "))
	   for(int j=1;j<=m;j++)
	     printf("%-5d",ans[i][j]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

总结，马的遍历问题，存储采用的是结构体，目的是在后续广度搜索时，能够坐标的位置状态。搜索里面的if()对于条件成立的判断：没有出界且该点没有被访问过。

接着更新一下洛谷p1036题解。
用到的算法是dfs。先上AC代码

#include<bits/stdc++.h>
using namespace std;
bool isprime(int n){
	for(int i=2;i<=sqrt(n);i++)
	 if(n%i==0) return false;
	 return true;
}
const int maxn=25;
int n,k;
int a[maxn];
long long ans;
void dfs(int m,int sum,int startx){
	if(m==k){
		if(isprime(sum)) ans++;
		return;
	}
	for(int i=startx;i<n;i++)
	   dfs(m+1,sum+a[i],i+1);
	return;
}
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++)
       cin>>a[i];
    dfs(0,0,0);
    cout<<ans;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

对于本题来说重点是dfs的写法。在这里我总结一下思路。
（1）参数m表示当前参与加法运算的操作数个数。简单的说，就是等号左边有几个数，sum用来表示当前等式左边的值。startx的作用是标记当前进行相加操作的数的序号。
（2）利用循环递归调用，避免了求组合。函数调用过程大致如下，首先取输入的第一个数，然后递归调用取第二个数，接着进行下一次递归调用（由于每次递归调用时，startx++因此不会出现一个数出现两次）。当进行第三次递归调用的时候，遇到终点会返回到第二层。接着第二层调用由于i++,即又进行了一次新的递归调用。以此类推。