bfs&dfs模板

摘自几个月前的帖子。。。
DFS模板：向深处搜索，直到找到解或者走不下去。这一般解决全排列问题

//No.1
Void DFS（deep，...）{
  if(找到解 || 走不下去了){
   ......//根据题意添加
    return; 
  }
  for(扩展方式){
   if(扩展方式所能达到的状态合法){
      修改操作；//根据题意添加
      标记；
      DFS(deep+1,...);
      //根据题意是否要还原
    }  
  } 
}
//No.2
int check(参数) {
	if(满足条件)
		return 1;
	return 0;
}

void dfs(int step) {
	判断边界 {
		相应操作
	}
	尝试每一种可能 {
		满足check条件
		标记
		继续下一步dfs(step+1)
		恢复初始状态（回溯的时候要用到）
	}
}

BFS模板：通常用队列先进先出实现，解决最小时间/最小步数

void BFS(){
 初始化队列Q;
 起点S入队;
 标记S已经访问;
 while(Q非空){
   取Q的队首元素U;
   U出队列;
   if(u==目标状态){
     返回结果；
    }
   for(所有与U相邻的元素){
     if(相邻的元素合法 && 未访问){
        入队;
        标记访问;
       }
   }
 }
}