DFS深度优先搜索

DFS(Depth-First-Search)深度优先搜索，是一种用于遍历或者搜索树或者图的算法。
DFS的基本思想如下：

int check(参数){
    if(满足条件)
        return 1;
    else 
        return 0;
}
void dfs(int step){
    判断边界{
        相应操作;
    }
    尝试每一种可能性{
        满足check条件;
        标记;
        继续下一步dfs(step+1);
        恢复到初始状态;
}

用递归实现DFS比较好理解，一直向下搜索，走不通之后就回到上一步尝试其它路径能否走通，一个DFS一般要判断边界，check用来判断是否符合相应的条件。
标记恢复相当于回溯的思想。
回溯法是一种优选的搜索法，又称为试探法，按照优选条件向前搜索，以达到目标。但是当探索到某一步时，发现原先选择并不优或者达不到目标，就退回一步重新选择，这种走不通就退回上一步重新选取路径试探的方法称为回溯法，而满足回溯条件的某个状态的点称为"回溯点"。