DFS & BFS Example

DFS
easy:
Oil Deposits https://vjudge.net/problem/HDU-1241#author=prayerhgq

normal:
Connect https://vjudge.net/problem/CodeForces-1130C#author=XMIWmayIsWorld
大臣的旅费 http://www.dotcpp.com/oj/problem1438.html
Sum in the tree https://vjudge.net/problem/CodeForces-1098A

BFS
easy:
迷宫问题 https://vjudge.net/problem/POJ-3984
Red and Black https://vjudge.net/problem/POJ-1979#author=s19435631
学霸的迷宫 http://www.dotcpp.com/oj/problem1923.html

normal:
Eight II https://vjudge.net/problem/HDU-3567

 

DFS

int dfs(int crt) {
    // 进入状态前
    if (/*如果已经记录了数据*/) // 返回存储了的数据(记忆化)

    // 处理状态中
    // 检查是不是答案
    // 可行性检查、最优性检查等

    // 离开状态后
    // 寻找之后的状态
    for (/*iterate every choice*/) {
        if (/*可达性判断*/) {
            /*vis等标记处理*/
            // 进入相邻的状态
            dfs(next_state);
            /*无效标记还原(backtrack)*/
        }
    }
}

 

 

BFS

void bfs() {
    queue<T> q;
    q.push(/*构建初始队列*/);

    while (!q.empty()) {
        // 状态前,获得当前状态属性等操作
        crt = q.front();
        q.pop();

        // 处理状态中
        if (/*达到解*/) {
            /*找到解后的操作*/
        }

        // 状态后,将相邻状态加入队列
        for (/*枚举每一种相邻状态*/) {
            if (/*可达性、最优性、有效性等的检测*/) {
                /*更新标记*/
                q.push(/*新状态*/);
            }
        }

    }
}