Like any good boss, the Chef has delegated all cooking jobs to his employees so he can take care of other tasks. Occasionally, one of the cooks needs a tool that is out of reach. In some of these cases, the cook cannot leave their workstation to get the tool because they have to closely watch their food. In such cases, the Chef simply fetches the tool for the cook.

Unfortunately, many different cooks have simultaneously requested a tool they cannot reach. Thankfully, no two cooks requested the same tool. Nobody else is available to help the Chef so he has to deliver all of the tools himself. He has to plan a trip around the kitchen in such a way that he picks up each tool and delivers it to the requesting cook. Since the Chef has two hands, he may carry up to two tools at once.

Once the last item has been delivered, the Chef also has to return to his starting position. This must be done as fast as possible so the Chef wants to do this while traveling the minimum possible distance.

------ Input ------ 

The first line contains a single integer T ≤ 20 indicating the number of test cases. Each test case begins with a single integer n, between 1 and 8, indicating the number of requests being made. The following n lines describe the locations of cooks and the tools they request. The i'th such line begins with two integers c_{x},c_{y} describing the location of the cook and ends with two more integers t_{x},t_{y} describing the location of the corresponding requested tool. No tool will be located at the same location as the cook who requests it.

The values c_{x}, c_{y}, t_{x}, and t_{y} corresponding to any cook or tool will always lie between 0 and 1000 (inclusive).
Finally, the kitchen is laid out into square workstations on a grid so the distance between two points x,y and x',y' is precisely their Manhattan distance |x-x'| + |y-y'|.

------ Output ------ 

The output for each test case consists of a single line. This line should display a single integer indicating the minimum distance the Chef must travel to deliver the tools to the cooks and return to his start location 0,0. Of course, he may only deliver a tool to a cook if he has already picked up the tool and he may not carry more than two tools at a time.

----- Sample Input 1 ------ 
3
2
1 0 0 1
0 0 1 1
3
0 3 0 1
0 4 0 2
0 5 0 3
3
0 1 0 2
0 1 0 2
0 1 0 2
----- Sample Output 1 ------ 
4
10
6
----- explanation 1 ------ 

In the second case, the Chef dropped of the first tool to the first cook and then picked up the tool for the third cook.

In the last test case, there are three different cooks requesting three different tools. It just so happens that all three tools are at the same location. Still, the Chef can only carry two of the tools from this location at once.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Paths and circuits

Graph traversal

Graph algorithms
Skill types: Dynamic programming

Starter code:

Solutions:
def dist(pos1: list, pos2: list) -> int:
	return abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1])

def list2bin(n: int, lst: list) -> str:
	num = 0
	for x in lst:
		num += 1 << x
	return f'{num:08b}'

def pos2str(pos: list) -> str:
	return '--'.join(map(str, pos))

def min_chef(chefs: list, tools: list, htools: list, rem_tools: list, pos: list, cost: int, dp: dict) -> tuple:
	hkey = list2bin(len(tools), htools)
	rkey = list2bin(len(tools), rem_tools)
	pkey = pos2str(pos)
	for (i, ti) in enumerate(htools):
		c = chefs[ti]
		dc = dist(pos, c)
		nhtools = htools[:i] + htools[i + 1:]
		hkey = list2bin(len(tools), nhtools)
		rkey = list2bin(len(tools), rem_tools)
		pkey = pos2str(c)
		if not dp.get(hkey, {}).get(rkey, {}).get(pkey):
			dp = recurse(chefs, tools, nhtools, rem_tools, c, dp)
		cost = min(cost, dc + dp[hkey][rkey][pkey])
	return (cost, dp)

def min_tool(chefs: list, tools: list, htools: list, rem_tools: list, pos: list, cost: int, dp: dict) -> tuple:
	for (i, ti) in enumerate(rem_tools):
		t = tools[ti]
		dt = dist(pos, t)
		nhtools = htools + [ti]
		nrem_tools = rem_tools[:i] + rem_tools[i + 1:]
		hkey = list2bin(len(tools), nhtools)
		rkey = list2bin(len(tools), nrem_tools)
		pkey = pos2str(t)
		if not dp.get(hkey, {}).get(rkey, {}).get(pkey):
			dp = recurse(chefs, tools, nhtools, nrem_tools, t, dp)
		cost = min(cost, dt + dp[hkey][rkey][pkey])
	return (cost, dp)

def recurse(chefs: list, tools: list, htools: list, rem_tools: list, pos: list, dp: dict) -> dict:
	hkey = list2bin(len(tools), htools)
	rkey = list2bin(len(tools), rem_tools)
	pkey = pos2str(pos)
	if hkey not in dp:
		dp[hkey] = {}
	if rkey not in dp[hkey]:
		dp[hkey][rkey] = {}
	if pkey not in dp[hkey][rkey]:
		if len(htools) > 2:
			cost = 1000000000.0
		elif len(htools) == 0 and len(rem_tools) == 0:
			cost = abs(pos[0]) + abs(pos[1])
		else:
			(cost, dp) = min_chef(chefs, tools, htools, rem_tools, pos, 1000000000.0, dp)
			(cost, dp) = min_tool(chefs, tools, htools, rem_tools, pos, cost, dp)
		dp[hkey][rkey][pkey] = cost
	return dp

def solve(chefs: list, tools: list, n: int) -> int:
	rem_tools = list(range(n))
	dp = recurse(chefs, tools, [], rem_tools, [0, 0], {})
	hkey = list2bin(n, [])
	rkey = list2bin(n, rem_tools)
	pkey = pos2str([0, 0])
	return dp[hkey][rkey][pkey]

def main():
	t = int(input().strip())
	for _ in range(t):
		n = int(input().strip())
		(chefs, tools) = ([], [])
		for i in range(n):
			(cx, cy, tx, ty) = map(int, input().strip().split())
			chefs.append([cx, cy])
			tools.append([tx, ty])
		print(solve(chefs, tools, n))
main()