Codechef June 2013 Elephants

	# wrong answer
	# standard DP problem with a twist.
	# the approach I chose:
	# 1. create an influence map not unlike those in game AI
	# 2. add the influence value at every point of the path
	# 3. deduct appropriate values when a mouse is double-counted
	# the rules for detecting double-counting mice:
	# 1. if a mouse moves right from tile x1 to tile x2 and there
	# is a mouse at x2, deduct 1
	# 2. if a mouse moves down from tile y1 to tile y2 and there
	# is a mouse at y2, deduct 1
	# 3. if a mouse moves from tile t to any tile, and there is a
	# mouse at t, deduct 1
	import sys
	T = int(sys.stdin.readline().strip())
	for t in xrange(T):
	n,m = sys.stdin.readline().strip().split()
	n,m = int(n), int(m)
	mapp = []
	# read map
	for i in xrange(n):
	mapp.append(sys.stdin.readline().strip())
	# create influence map
	influence = []
	for i in range(n):
	influence.append([0] * m)
	for y in xrange(n):
	for x in xrange(m):
	if mapp[y][x] == "1":
	influence[y][x] += 1
	if x-1 >= 0:
	influence[y][x-1] += 1
	if y-1 >= 0:
	influence[y-1][x] += 1
	if x+1 < m:
	influence[y][x+1] += 1
	if y+1 < n:
	influence[y+1][x] += 1
	# run DP
	dp = []
	for i in range(n):
	dp.append([0] * m)
	for y in xrange(n):
	for x in xrange(m):
	dp[y][x] += influence[y][x]
	# from left
	if x-1 >= 0:
	fromleft = dp[y][x-1]
	# rule 1
	if mapp[y][x] == "1":
	fromleft -= 1
	# rule 3
	if mapp[y][x-1] == "1":
	fromleft -= 1
	# from top
	if y-1 >= 0:
	fromtop = dp[y-1][x]
	# rule 2
	if mapp[y][x] == "1":
	fromtop -= 1
	# rule 3
	if mapp[y-1][x] == "1":
	fromtop -= 1
	if x-1 < 0 and y-1 < 0:
	pass
	elif x-1 < 0:
	dp[y][x] += fromtop
	elif y-1 < 0:
	dp[y][x] += fromleft
	else:
	dp[y][x] += min(fromtop,fromleft)
	print dp[y]
	print

view raw gistfile1.txt hosted with ❤ by GitHub

	# time limit exceeded for some reason
	# tested with 100x100 map and it runs fine locally
	# updated according to the editorial
	# catered to handle double-counting when turning a corner
	# without passing through mouse
	# standard DP problem with a twist.
	# the approach I chose:
	# 1. create an influence map not unlike those in game AI
	# 2. add the influence value at every point of the path
	# 3. deduct appropriate values when a mouse is double-counted
	# the rules for detecting double-counting mice:
	# 1. if a mouse moves right from tile x1 to tile x2 and there
	# is a mouse at x2, deduct 1
	# 2. if a mouse moves down from tile y1 to tile y2 and there
	# is a mouse at y2, deduct 1
	# 3. if a mouse moves from tile t to any tile, and there is a
	# mouse at t, deduct 1
	import sys
	T = int(sys.stdin.readline().strip())
	for t in xrange(T):
	n,m = sys.stdin.readline().strip().split()
	n,m = int(n), int(m)
	mapp = []
	# read map
	for i in xrange(n):
	mapp.append(sys.stdin.readline().strip())
	# create influence map
	influence = []
	for i in range(n):
	influence.append([0] * m)
	for y in xrange(n):
	for x in xrange(m):
	if mapp[y][x] == "1":
	influence[y][x] += 1
	if x-1 >= 0:
	influence[y][x-1] += 1
	if y-1 >= 0:
	influence[y-1][x] += 1
	if x+1 < m:
	influence[y][x+1] += 1
	if y+1 < n:
	influence[y+1][x] += 1
	# run DP
	dp = []
	for i in range(n):
	b = []
	dp.append(b)
	for j in range(m):
	b.append([0,0]) # 0 for left, 1 for top
	for y in xrange(n):
	for x in xrange(m):
	dp[y][x][0] += influence[y][x]
	dp[y][x][1] += influence[y][x]
	# from left
	if x-1 >= 0:
	fromleft = min(dp[y][x-1][0], dp[y][x-1][1]-int(mapp[y-1][x]) if y-1 >= 0 else dp[y][x-1][1])
	# rule 1
	if mapp[y][x] == "1":
	fromleft -= 1
	# rule 3
	if mapp[y][x-1] == "1":
	fromleft -= 1
	# from top
	if y-1 >= 0:
	fromtop = min(dp[y-1][x][1], dp[y-1][x][0]-int(mapp[y][x-1]) if x-1 >= 0 else dp[y-1][x][0])
	# rule 2
	if mapp[y][x] == "1":
	fromtop -= 1
	# rule 3
	if mapp[y-1][x] == "1":
	fromtop -= 1
	if x-1 < 0 and y-1 < 0:
	pass
	elif x-1 < 0:
	dp[y][x][1] += fromtop
	dp[y][x][0] += fromtop
	elif y-1 < 0:
	dp[y][x][0] += fromleft
	dp[y][x][1] += fromleft
	else:
	dp[y][x][0] += fromleft
	dp[y][x][1] += fromtop
	#print dp[y]
	print min(dp[y][x][0], dp[y][x][1])

view raw gistfile1.txt hosted with ❤ by GitHub