DFS

介绍:深度优先搜索是搜索的手段之一,它从某个状态开始,不断的转移状态直至无法转移,然后不断回到上一个状态,深度优先搜索从最开始的状态出发,遍历所有可以达到的状态.由此可以对所有的状态进行操作,或列举出所有的状态;
例题讲解:
问题:

Due to recent rains, water has pooled in various places in Farmer John’s field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water (‘W’) or dry land (’.’). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors.Given a diagram of Farmer John’s field, determine how many ponds he has.

分析:利用深度优先搜索进行一片水域遍历,从头使用dfs的次数就是水泊的个数;

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int slen = 1e2+5;
char map[slen][slen];
int d[7] = {1,0,-1};
void dfs(int x,int y)
{
	map[x][y] = '.';
	for(int i = 0;i < 3;++i)
		for(int j = 0;j < 3;++j)
		if(map[x+d[i]][y+d[j]] == 'W')
		dfs(x+d[i],y+d[j]);
}
int main()
{
		int n,m;cin >> n >> m;
		for(int i = 1;i <= n;++i)
			scanf("%s",map[i]+1);
		int ans = 0;
		for(int i = 1;i <= n;++i)
			for(int j = 1;j <= m;++j)
			if(map[i][j] == 'W')
			{
				++ans;
				dfs(i,j);
			}
		cout << ans << endl;
	return 0;
 }  

BFS

介绍:宽度优先搜索也是搜索的手段之一,于深度优先搜索不同的是,宽度优先搜索总是先搜索距离初始状态较近的状态,对于同一个状态,宽度优先搜索只经历一次,因此时间复杂度为O(状态数*转移方式数).
例题讲解:
题目:

There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can’t move on red tiles, he can move only on black tiles.
Write a program to count the number of black tiles which he can reach by repeating the moves described above.

分析:使用宽度优先搜索转移状态,由于每个黑方块只达到一次,达到每个方块后进行统计就可以得到答案;

#include<algorithm>
#include <utility>  
#include <iostream>  
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef pair<int,int> P;
char land[25][25];
int main()
{
	int n,m;cin >> m >> n;
	while(m||n)
	{
	for(int i = 0;i < 25;++i)for(int j = 0;j < 25;++j)land[i][j] = '@';
	for(int i = 1;i <= n;++i) cin >> land[i]+1;
	int x,y,find = 0;
	for(int i = 1;i <= n&&!find;++i)
	for(int j = 1;j <= m&&!find;++j) 
	if(land[i][j] == '@')
	{
		x = i;
		y = j;
		find = 1;
	}
	queue<P>que;
	que.push(P(x,y));
	int ans = 0;
	while(que.size())
	{
		++ans;
		P p = que.front();que.pop();
		if(land[p.first-1][p.second] == '.')
		{
			que.push(P(p.first-1,p.second));
			land[p.first-1][p.second] = '@';
		}
		if(land[p.first+1][p.second] == '.')
		{
			que.push(P(p.first+1,p.second));
			land[p.first+1][p.second] = '@';
		}
		if(land[p.first][p.second-1] == '.')
		{
			que.push(P(p.first,p.second-1));
			land[p.first][p.second-1] = '@';
		}
		if(land[p.first][p.second+1] == '.')
		{
			que.push(P(p.first,p.second+1));
			land[p.first][p.second+1] = '@';
		}
	}
	cout << ans << endl;
	cin >> m >> n;
}
	return 0;
}

二分

介绍:利用单调性不断缩小解可以存在的范围,从而到达最优解的方法;
题目讲解:

Obs: this is an interactive problem. More information is under the “Interaction” section.
MaratonIME is gathering to start another group practice. This time, Renzo decided to reward the students with candies as they solve problems. Curious as they are, the members of MaratonIME started to guess how many candies did Renzo bring. For each question, Renzo answered if the amount of candies was higher, lower or equal to the number asked.
Breno, noticing that the amount of candies could be very high, decided to limit the number of queries to 50. This way, the practice would start as soon as possible.
Renzo bought at least 1 and no more than 109 candies. Find how many candies were bought by Renzo with no more than 50 questions.

分析:
二分，每次询问mid，如果是>就找左边，是<就找右边，直到找到为止。

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
	int t = 50;
	int head = 1,tail = 1e9+1;
	while(t--)
	{
		cout << 'Q' << ' ' << (head+tail)/2 << endl;
		char t;cout.flush();cin>>t;
		if(t == '>')
			head = (head+tail)/2;
		else if(t == '<')
			tail = (head+tail)/2;
		else
			break;
	}
	return 0;
 } 

总结:dfs和bfs可以用来遍历问题的所有可能解来得到解,二分可以利用单调性来快速得到问题的解;