Optimally pop all the bubbles

Question

In a given 2d grid of positive integers (representing different types of "bubbles"), there are one of two actions that you can do each "step". You can either:

1. Pop an island (a connected group of bubbles - two bubbles that are diagonally adjacent are not considered connected) of the same type of bubbles, given that the island consists of at least 2 bubbles AND at least one bubble in said island has no bubbles above it.

Or,

2. Drop a single bubble of any type into any column, given that the chosen column is not filled to the top of the grid.

After one of these two steps, all bubbles will fall towards the bottom of the grid, and the next step will start.

The grid can also include 0's, which represent empty space.

Task

Your task is: Given a \$m\times n\$ 2d grid of positive integers representing a grid of bubbles and the optional \$m\$ and \$n\$ and input, determine the fewest amount of moves in which the entire grid can be cleared of bubbles. The input grid is guaranteed to be clearable.

Worked example

22222
21212
22222
21212
22222

The first step will be to first pop the island of 2's. After all the bubbles have fallen, the grid will then look like this, where the 0's represent empty space:

00000
00000
00000
01010
01010

The second step will be to drop a 1 bubble in the middle column, so that the grid now looks like this:

00000
00000
00000
01010
01110

And the final step is to pop the island of 1's, clearing the entire grid.

Test Cases

m, n
grid
-> output

5, 5
22222
21212
22222
21212
22222
-> 3

7, 7
1111111
2222222
1111111
2222222
1111111
2222222
1111111
-> 7

7, 6
000000
121212
212121
121212
212121
121212
212121
-> 22

2, 7
0000000
1000001
-> 4

8, 1
0
1
2
2
2
2
2
1
-> 5

8, 2
00
10
20
20
20
20
20
10
-> 4

If any of y'all need it, I also made a (pretty bad) tool that will take in a list of steps (more info in the TIO link) and output the board state after those steps have been taken: Try It Online!

---

This is code-golf, so the shortest solution in bytes for each language wins!

Answer 1

Python3, 901 bytes:

E=enumerate
def B(b):
 P,R,s=[(x,y)for x,j in E(b)for y,k in E(j)if k],[],[];p=P
 while p:
  x,y=p[0];q=[(x,y)];s+=p[0],
  while(o:=[X for x,y in q for X in[(x+1,y),(x,y+1),(x-1,y),(x,y-1)]if X in P and b[x][y]==b[X[0]][X[1]]and(X in s)^1]):q+=o;s+=o
  R+={*q},;p=[i for i in p if(i in s)^1]
 return R
F=lambda b:[*map(list,zip(*[[0]*i.count(0)+[j for j in i if j]for i in zip(*b)]))] 
def f(b):
 q,S=[(b,0)],{}
 while q:
  b,c=q.pop(0)
  if sum(sum(b,[]))<1:return c
  I=B(b)
  for i in I:
   if len(i)>1and sum(all(b[x-t][y]==b[x][y]or 1>b[x-t][y]for t in range(x+1))for x,y in i):
    W=eval(str(b))
    for x,y in i:W[x][y]=0
    if(str(w:=F(W))in S)^1or-~c<S[str(w)]:q+=(w,c+1),;S[str(w)]=c+1
  for y,C in E(zip(*b)):
   if C[0]<1:
    for v in{j for k in b for j in k if j}:
     W=eval(str(b));W[0][y]=v
     if(len(B(e:=F(W)))<=len(I))&((str(e)in S)^1or-~c<S[str(e)]):q+=(e,c+1),;S[str(e)]=c+1

Try it online!