python-剪格子

解题思路:

bfs。

先强调一点，题目是先输入的列数，后输入的行数，不要搞反了。

①求出所给矩阵的和，如果和为奇数，无法分割。如果和为偶数，进行下一步。

②从第0行第0列开始进行深度搜索。如果搜索到某一个数值时，和为矩阵和的一半，则对最小格子数进行比较，更新。

最后输出答案即可

注意事项:

参考代码:

from cmath import inf    
     
def dfs(x,y,now,cnt):     #四个参数分别为当前点的x坐标，y坐标，到当前点的和，到当前点包含的格子数  
    global n,m,Marix,Visit,sum_num,minnum  
  
    if now > sum_num:  
        return  
     
    if now == sum_num:    
        if cnt < minnum:    
            minnum = cnt    
        return    
         
    D = [(-1,0),(1,0),(0,-1),(0,1)]    
    for i in range(4):       #上下左右  
        x_now = x+D[i][0]    
        y_now = y+D[i][1]    
        if (0<= x_now <= n-1) and (0<= y_now <= m-1) and Visit[x_now][y_now]:    
            Visit[x_now][y_now] = 0    
            dfs(x_now,y_now,now+Marix[x_now][y_now],cnt+1)    
            Visit[x_now][y_now] = 1    
         
     
if __name__ == '__main__':    
    m,n = map(int,input().strip().split())    
    Marix = [[int(j) for j in input().strip().split()] for i in range(n)]  #记录矩阵  
    Visit = [[1 for j in range(m)] for i in range(n)]    #访问数组  
    sum_num = 0    
    for i in range(n):  #求矩阵和  
        sum_num = sum_num + sum(Marix[i])    
    minnum = inf    
    if sum_num % 2 == 1:    
        print(0)    
    else:    
        sum_num = sum_num//2    
        Visit[0][0] = 0    
        dfs(0,0,Marix[0][0],1)  #进入搜索  
        if minnum == inf:    
            print(0)    
        else:    
            print(minnum)