<commit_before>---
layout: post
category: Algorithms
title: BFS
tags: Algorithms
---

## BFS

bfs可以求一些复杂的最短路径。模板就是使用优先队列，同时记录是否访问过，每次弹出最短的那一个，持续更新到终点。这也是dijkstra.

比如，[求最少转弯的路径](https://mafulong.top/2018/08/27/bfs%E6%9C%80%E5%B0%8F%E8%BD%AC%E5%BC%AF%E8%B7%AF%E5%BE%84/)

以及，[1368. 使网格图至少有一条有效路径的最小代价](https://leetcode-cn.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/)



## 0-1 广度优先搜索

参考：[https://leetcode-cn.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/solution/shi-wang-ge-tu-zhi-shao-you-yi-tiao-you-xiao-lu-2/](https://leetcode-cn.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/solution/shi-wang-ge-tu-zhi-shao-you-yi-tiao-you-xiao-lu-2/)

为了可以处理权值为0的边，使用双端队列，当遇到是0的边，就加入到队首。
<commit_msg>add logbook<commit_after>---
layout: post
category: Algorithms
title: BFS
tags: Algorithms
---

## BFS

bfs可以求一些复杂的最短路径。模板就是使用优先队列，同时记录是否访问过，每次弹出最短的那一个，持续更新到终点。这也是dijkstra.

比如，[求最少转弯的路径](https://mafulong.github.io/2018/08/27/bfs%E6%9C%80%E5%B0%8F%E8%BD%AC%E5%BC%AF%E8%B7%AF%E5%BE%84/)

以及，[1368. 使网格图至少有一条有效路径的最小代价](https://leetcode-cn.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/)



## 0-1 广度优先搜索

参考：[https://leetcode-cn.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/solution/shi-wang-ge-tu-zhi-shao-you-yi-tiao-you-xiao-lu-2/](https://leetcode-cn.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/solution/shi-wang-ge-tu-zhi-shao-you-yi-tiao-you-xiao-lu-2/)

为了可以处理权值为0的边，使用双端队列，当遇到是0的边，就加入到队首。

{'fraction_non_alphanumeric': 0.2053805774278215, 'fraction_numerical': 0.04199475065616798, 'mean_word_length': 4.842911877394636, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 8, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4925559', 'n_tokens_mistral': 943, 'n_tokens_neox': 948, 'n_words': 37}