-6 bytes thanks to @Kevin Cruijssen
-43 bytes thanks to @Jitse
import numpy
z=len
d=lambda a,b,c,d:abs(a-c)+abs(b-d)
def g(l,m):
if z(l)==1:yield d(*l[0],*m[0])
for i in range(z(l)):
for s in g(l[1:],m[:i]+m[i+1:]):yield d(*l[0],*m[i])+s
def c(a,b):
e=a-b;k=z(a);f,*h=[],
for x in range(k*z(a[0])):w=[(x%k,x//k)];v=e[x%k][x//k];f+=w*(v>0);h+=w*(v<0)
return-1 if numpy.sum(e)else min(g(f,h))
Try it online!
Takes input as two numpy arrays.
Explanation:
First, e=a-b
determines which positions change from one grid to the other.
The next line finds all of the differences and sorts them into the lists f
and h
. If the sum of differences is not zero, meaning there are more 1s in
one grid than the other, this returns -1
, or the minimum of all possible
paths found by g
.
This is the fun part. Essentially, in order to make this work, a 1 must move from one position to another by swapping. Therefore, the minimum number of swaps for each pair is the manhattan distance between them, found in d
. g
finds every possible pairing between start and end points and returns a list
of the total distances between them. If there is only one start point, it returns the distance between that and the end point. Beyond that, it pairs the first start point with each end point iteratively and adds their distance to the total distance of the rest of the points, calculated recursively.