有不足之处请指出啦,多谢大佬指点^_^
搜索的部分题型
1.棋盘类与格子类 根据题目需求用dfs/bfs
dfs
dfs就是一条路走到黑,一定可以找到解,然后通过回溯来找到更多的解
dfs感觉一般会使用递归,所以代码看起来总是比bfs要复杂(猪脑过载ing。。。)
如846(数的重心)
ps:这道题由于用的是无相图,要注意防止它往回走造成死循环
首先从第一个数1开始,然后遍历其所有统领的节点(直连)(这里有一个递归进程),其中dfs可以直接返回这个数下有多少个节点,然后求出所有直连子节点所在联通块中节点的数量和父节点(也可能没有父节点)所在联通块中节点的数量,求最大值
最后遍历所有的点求这个最大值的最小值
在另如1112(迷宫,连通性模型),1113(红与黑)
这种题咋一看是像bfs的走迷宫,但是不要求求最短路径(这不废话吗)
这种格子型的题,是以每一个节点向四周递归搜索,这种情况不需要恢复现场(而如843八皇后问题这种棋盘问题就需要恢复现场)
1112这种题是只要判断是否有条通路,以每个点为节点,向周围递归搜索即可
1113这种题要计数,以每个点为节点,每遍历到一个可用节点,为答案加一
bfs
bfs与dfs不同,bfs是一层层的遍历,因此可以找出最短路径
bfs感觉一般会使用队列,至少现在做的几道题都用了()
如847(图中点的层次)
首先先从第一个数1开始,先遍历其所有直连的节点,如果这个点为遍历过,就记录上离第一个数的距离并且将其加入队列等待进行遍历其直连节点,然后弹出这个数字。遍历下一个数字直到队列中无可遍历的点(q.size() == 0)
最后输出目标点与第一个点的距离。