蓝桥杯-剪格子

import os
import sys
ans = 0
m,n = map(int,input().split())
mp = [[int(j)for j in input().split()]for i in range(n)]
flag = [[0]*(m)for i in range(n)]
for i in range(n):
    for j in range(m):
        ans+=mp[i][j]
z = []
d = [[1,0],[-1,0],[0,1],[0,-1]]
def dfs(x,y,res,cnt):
    if res == ans//2:
        z.append(cnt)
        return
    for a,b in d:
        newx,newy = x+a,y+b
        if newx>=0 and newx<n and newy>=0 and newy<m \
           and flag[newx][newy]==0:
            cnt+=1
            res+=mp[newx][newy]
            flag[x][y] = 1
            dfs(newx,newy,res,cnt)
            res-=mp[newx][newy]
            flag[x][y] = 0
            cnt-=1
if ans%2 !=0:
    print(0)       
else:
    dfs(0,0,mp[0][0],1)
    print(min(z))