Identical grids

Question

You’re given two \$r×c\$ grids. Each cell contains either 0 or 1. What are the minimum number of swaps (between horizontally and vertically adjacent cell elements, no wrapping i.e no swapping between last and first element of a row) are required in the first grid for it to match the second. If the matched arrangement can never be achieved, output -1.

Constraints

\$1 \leq r \leq 100\$
\$1 \leq c \leq 100 \$

Examples

input:
00  
11  

01  
10  
output:
1  

input:
00  
11  

01  
00  
output:
-1  

input:
0011011  

0101101  
output:
2 

Answer 1

Python 3, 383 334 bytes

-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.

Answer 2

APL (Dyalog Extended), 35 bytes

{⍺≠⍥≢⍵:¯1⋄⌊/⍺[⌂pmat≢⍺]+.(1⊥∘|-)⍵}⍥⍸

Try it online!

A function that takes two Boolean matrices as left and right arguments.

Uses Hiatsu's algorithm. One additional thing to point out is that, while moving a 1 from some position to another, it may freely step over some ones and still take the same steps. Therefore, the pairwise Manhattan distances can be summed without interfering each other. (This doesn't invalidate the previous answers; rather, it covers a hole in the proof that the algorithm is indeed correct.)

Moving the one at the start to the end:
1 0 0 0 0 1 1 1 0 0 0
^------->              Move the 1 four steps forward
0 0 0 0 1 1 1 1 0 0 0
        <-------^      Move the 0 four steps backwards
0 0 0 0 0 1 1 1 1 0 0  (See that the target 1 has moved 4 steps forward as net effect)
                ^--->  Finally move the 1 to the destination
0 0 0 0 0 1 1 1 0 0 1
So the 1 has travelled the distance of 10 in 10 steps, stepping over ones

How it works: the code

{⍺≠⍥≢⍵:¯1⋄⌊/⍺[⌂pmat≢⍺]+.(1⊥∘|-)⍵}⍥⍸  ⍝ Main function
{                               }⍥⍸  ⍝ Extract coordinates of ones from both args
 ⍺≠⍥≢⍵:     ⍝ If the lengths (count of ones) do not match,
       ¯1   ⍝ Return minus 1
         ⋄  ⍝ Otherwise,
            ⍺[⌂pmat≢⍺]            ⍝ All permutations of coordinates of left arg
                      +.(1⊥∘|-)⍵  ⍝ Inner product with ⍵ to get Manhattan distance sum:
                        (1⊥∘|-)   ⍝ sum the absolute differences of coords point-wise
                      +.          ⍝ and sum all the distances
          ⌊/                      ⍝ Pick the minimum value

Answer 3

Based on @Hiatsu's answer.

Python 3, 262 bytes

e=enumerate
def f(r,s):
 if not r:yield 0
 for i,t in e(r):yield abs(t[0]-s[0][0])+abs(t[1]-s[0][1])+min(f(r[:i]+r[i+1:],s[1:]))
def g(x,y):
 z=x-y;n=len(x.T);v,*w=[],
 for i,p in e(z.flat):t=[(i%n,i//n)];v+=t*(p>0);w+=t*(p<0)
 return-1if z.sum()else min(f(v,w))

Try it online!