Submission #721116

---

Source Code Expand

MOD = 10**9+7
h,w = map(int,raw_input().split(' '))
maze = [map(int,raw_input().split(' ')) for i in xrange(h)]
def how_many(i,j):
	count = []
	dire = [[i-1,j],[i+1,j],[i,j+1],[i,j-1]]
	for k in xrange(4):
		if dire[k][0]<0 or dire[k][0]>=h or dire[k][1]<0 or dire[k][1]>=w:
			continue
		if maze[i][j]<maze[dire[k][0]][dire[k][1]]:
			count.append([dire[k][0],dire[k][1]])
	return count
children = [[how_many(j,i) for i in xrange(w)] for j in xrange(h)]
routs = [[None if children[i][j]!=0 else 0 for j in xrange(w)] for i in xrange(h)]
def how_many_all(i,j):
	count = 0
	for child in children[i][j]:
		if routs[child[0]][child[1]]==None:
			count += (how_many_all(child[0],child[1])+1)%MOD
		else:
			count += (routs[child[0]][child[1]]+1)%MOD
	routs[i][j] = count
	return count
count = 0
for i in xrange(h):
	for j in xrange(w):
		count+=(how_many_all(i,j)+1)%MOD
print count%MOD

Submission Info

Judge Result