class Solution:

# @param dungeon, a list of lists of integers

# @return a integer

def calculateMinimumHP(self, dungeon):

if dungeon==None:

return None

m=len(dungeon)

n=len(dungeon[0])

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

DP[m-1][n-1]=1-dungeon[m-1][n-1]

for i in range(m-1,-1,-1):

for j in range(n-1,-1,-1):

if i+1>=m and j+1<n:

DP[i][j]=DP[i][j+1]-dungeon[i][j]

elif i+1<m and j+1>=n:

DP[i][j]=DP[i+1][j]-dungeon[i][j]

elif i+1<m and j+1<n:

DP[i][j]=min(DP[i][j+1]-dungeon[i][j],DP[i+1][j]-dungeon[i][j])

if DP[i][j]<=0:

DP[i][j]=1

return DP[0][0]