蓝桥杯2013年第四届真题-剪格子（python代码）——菜鸟见解

解题思路:

注意事项:

多多优化

参考代码:

n,m = map(int,input().split())

data = [list(map(int,input().split())) for i in range(m)]

sums = sum([sum(data[i]) for i in range(m)])

bools = [[0 for i in range(n)] for j in range(m)]

res = 10000

def search(now,x,y,count,sign):

    global res

    if now > half or res <= count or bools[x][y]:

        return

    elif now == half:

        res = count

    now += data[x][y]

    bools[x][y] = 1

    count += 1

    if sign != "D" and x < m-1:

        search(now,x+1,y,count,"U")

    if sign != "R" and y < n-1:

        search(now,x,y+1,count,"L")

    if sign != "L" and y > 0:

        search(now,x,y-1,count,"R")

    if sign != "U" and x > 0:

        search(now,x-1,y,count,"D")

    if x < m-1 and y > 0:

        search(now,x+1,y-1,count,"LD")

    bools[x][y] = 0

if sums%2 != 0:

    print(0)

else:

    half = sums//2

    search(0,0,0,0,"U")

    if res == 10000:

        print(0)

    else:

        print(res)