题解 | 取数游戏

回溯法，确定一个点(i,j)后，从(i,j+1:)以及(i:,:)确认下一个点

T=int(input())
for i in range(T):  
    N,M=tuple(map(int,input().split()))
    matrix=[]
    for j in range(N):
        matrix.append(list(map(int,input().split())))
    ans=0
    def possible(y,x,posSet):
        for i,j in [(y-1,x-1),(y-1,x),(y-1,x+1),(y,x-1)]:
            if i<0 or j<0:
                continue
            if (i,j) in posSet:
                return False
        return True

                


    def backtracking(row,col,total,posSet):
        global ans
        ans=max(ans,total)

        for i in range(row,N):
            for j in range(M):
                if i==row and j<col:
                    continue
                else:
                    if possible(i,j,posSet):
                        posSet.add((i,j))
                        backtracking(i,j+1,total+matrix[i][j],posSet)
                        posSet.remove((i,j))

    backtracking(0,0,0,set())
    print(ans)