bfs和dfs板子

• 过了一个月，bfs和dfs复习，手打一遍板子。。。

BFS

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool vis[...]; //用来去重
int dir[...][...] = {...}; //定义方向的数组

struct node{ //定义状态的结构体
	int x,y,...; //定义方向属性
	int step; //用来存步数（因为bfs一般是求最短路）
};

void bfs(有必要的情况下需要传参){
	queue <node> q;
	start.step = 0;
	...
	q.push(start);
	...
	while(!q.empty()){
		node q1 = q.front();
		q.pop();
		if(q1.某状态（通常是step）==目标状态){
			处理或不处理；
			return;
		}
		node v;
		for(int i=0;i<...;i++){
			int dx = q1.x + dir[...][0];
			int dy = q1.y +dir[...][1];
			...;
			if(不满足条件) continue;
			vis[...] = 1;
			v.step = q1.step + 1;
			v.x = dx, v.y = dy;
			对答案做处理
			q.push(v);
		}
	}
}

int main(){
	处理输入;
	bfs(参数)；
	处理输出;
	return 0;
}

DFS

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool vis[...]; //用来去重
int dir[...][...] = {...}; //定义方向的数组
bool f = false; //剪枝

void dfs(参数){
	if(f){ //剪枝
		return ...;
    }
    if(达到目标状态){
        处理答案;
        f = true;
        return ...;
    }
    for(遍历所有状态){
		if(合法&&!vis[...]){
		    vis[...] = 1; //标记走过
            处理;
            dfs(传参); //递归
            回溯（如果需要的话）;
        }
    }
    return ...;
}

int main(){
	处理输入;
    处理过程;
    dfs(传参);
    处理输出;
    return 0;
}