The walk determines the boundary of an area. Each square with a 0 must be outside that area,
and each square with a 1 must be inside, with the walk going around the square exactly once
in the clockwise direction. (Technically, we could go three times clockwise and twice
counterclockwise, but that's clearly suboptimal.)

For simplicity, assume that there are 0s everywhere around the given grid.
The 1s in the given grid form some connected components. Clearly, for each connected component
we have to walk along its entire boundary to separate the 1s it contains from 0s that surround
it. The total length of these steps is precisely the number of adjacent 0-1 pairs in the grid.
(I.e., we can compute it without bothering to find the connected components.)

Of course, that's not all yet. We need to actually reach each of the grid points at least once.
The cheapest way to do so can be found by computing the minimum spanning tree. The edges we
counted in the previous step are now free. All other edges have the cost 2, because if we use
such an edge, we have to use it later in the opposite direction as well.

For an even simpler implementation, just process the grid points in row major order. Each time you
discover
a point you haven't visited yet, you have to pay at least 2 to visit it -- and you can do that by
paying exactly 2 and reaching it from the already visited point above/to the left of it. And once
you can visit this point, you can visit all points reachable by cost-1 edges from it, so just run
a DFS to mark all those as visited. (The DFS will simply walk along the boundary of the currently found component
of 1s.)