深度优先搜索

排列、组合

A(n,m) = 在n个元素中选择m个进行排列

$$A(n,m) = n * (n-1) * ... * (n-m+1)$$

C(n,m) = 在n个元素中选择m个进行组合(无重复)

$$C(n,m) = A(n,m)/A(m,m) = [ n * (n-1) * ...* (n-m+1) ] / m!$$

组合排序(定序)：

int dfs(int i, int last)
{
	if(!i)
	{
		return 0;
	}
	else if(i == 1)
	{
		for(int d = last + 1; d <= k; d++)
		{
			if(use[d])
			{
				continue;
			}
			a[i] = d;
			int j = n;
			while(j--)
			{
				cout << a[j + 1] << " ";
			}
			cout << endl;
		}
		return 0;
	}
	else
	{
		for(int d = last + 1; d <= k; d++)
		{
			if(use[d])
			{
				continue;
			}
			a[i] = d;
			use[d] = 1;
			dfs(i - 1);
			use[d] = 0;
		}
		return 0;
	}
	return -1;
}

剪枝

过程中去掉超过范围的状态
可行性https://www.luogu.com.cn/problem/B3624
最优性https://www.acgo.cn/problemset/8051/info

连通性

bool vis[MAXX][MAXY];
char s[MAXX][MAXY];
int n, m;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};


bool dfs(int x, int y)
{
	vis[x][y] = 1;
	if(s[x][y] == 'g')
	{
		return 1;
	}
	else
	{
		for(int i = 0; i < 4; i++)
		{
			int to_x = x + dx[i];
			int to_y = y + dy[i];
			if(!vis[to_x][to_y] && to_x >= 1 && to_y >= 1 && to_x <= n && to_y <= m && s[to_x][to_y] !='#')
			{
				if(dfs(to_x, to_y))
				{
					return 1;
				}
			}
		}
		return 0;
	}
	return 0;
}