搜索小技巧

一个搜索要知道如何剪枝，但剪枝是一个难点。

在写搜索的时候，我们要想会不会有冗杂的多余的搜索产生，如果有，我们就可以用记忆化搜索/剪枝

或者说如果后面的条件可以包含于前面的，那我们就可以用剪枝来处理掉

如：

给定一个数m，我要在若干个数中，找到一些数，使他的重量最接近我们的m值
（用搜索）

一看到一个和，我们就要感性的想到用前缀和，如果我们所有的数加起来都要比我们的m小的话，那我们就可以用一个包含的思想来把这道题给剪枝掉。

if(sum[c-1]+x<=m){
	ans=max(ans,sum[c-1]+x);
	return;
}

之后是状态判断，如何更新答案或者是返回

返回很简单

if(x<1||x>m||y<1||y>m||c[i][j]==1)//这个c代表是否我们访问过

然后更新答案

if(...){
ans=...
}

DFS，BFS

在做题中要思考好是用dfs还是bfs

dfs一定不要忘了回溯

c[i][j]=0;

dfs在什么时候继续深入要好好想一想就是dfs(s+1,a)

这一块一定要搞清楚，要不永远做不会搜索

bfs用队列，dfs用栈（对应思想）

bfs和dfs的板子其实很简单，也没有什么改变

code: