回溯算法模板

//回溯算法，万能解题模板

void dfs(int step)  //准备在第 step 选择答案 
{
	if (step == 最后一个位置的下一个)
	{
		//输出答案，保存答案
		return ;	
	}	
	else
	{
		for (int i = 第一项; i <= 最后一项; i ++) //确保不重不漏 
		{
			if (第 i 个选项合法) 
			{
				保存现场; //设置一个标记，其他函数(本身）不能使用 
				dfs(step + 1);//回溯下一步
				恢复现场; //取消一个标记 ， 其他函数(本身）可以使用
			} 
		} 
	}
}

chen_zhe 沙雕

2020-05-30 20:49:17

骗分过样例，暴力出奇迹；爆搜挂着机，打表出省一

chen_zhe 沙雕

2020-05-30 20:44:56

深度优先搜索算法（dfs）模板二：

void dfs(int step){
        for(int i=1; i<=n（就是最后一个选项）; i++){ 
            if(第i个选项合法){ 
                保存当前状态，记录，后面的状态在回溯前不能使用该选项； 
                b[i]=1; //设置标记（一般使用数组）； 
                if(搜索完成（一般用step==n+1或step==n表示）){输出结果；   return;} 
                dfs(step+1) //继续向下深度搜索； 取消标记； 
                b[i]=0; //回溯前一个状态 
            } 
        }
}

Duke

2020-05-25 21:22:31

NBNB，谢谢老师

共 3 条回复