问题

给个网格，每个格子是0或1，你至少需要把多少0变成1才能通过走1的四联通从网格一边走到另一边？

题解

每个点可以和他的相邻的点连一条边

考虑最短路

如果某个点是1，那么到他不需要代价，否则需要1的代价（把这个点变成1）

添加一个起始点，和第一行的点连边，添加一个终点，和最后一行的点连边

考虑01bfs

开个双端队列存当前访问的点，如果当前边权是0，往队列头添加这个点，否则往队列尾添加这个点 这样每个点只会进出队列$O(1)O(1)$次

复杂度$O(NM)O(NM)$

吐槽

那个阿巴阿巴的语言病毒拥有者就是我其中一个亲爱的队友，托他的福大家逐渐开始丧失理解和表达能力，真是可喜可贺。