aoc21_15.awk

{
	gsub(/./, "& ")

	for(i = 1; i <= NF; i++)
		risk_level[i, NR] = $i
}

END {
	find_lowest_total_risk()

	expand_map()
	find_lowest_total_risk()
}

function find_lowest_total_risk() {
	while (dequeue());
	delete total_risk
	delete visited

	total_risk[1 SUBSEP 1] = 0
	enqueue(0, 1 SUBSEP 1)

	while ((cur = dequeue()) != NF SUBSEP NR) {
		split(cur, tmp, SUBSEP)
		x = tmp[1]
		y = tmp[2]

		delete neighbors
		if (x > 1)
			neighbors[x-1, y]
		if (x < NF)
			neighbors[x+1, y]
		if (y > 1)
			neighbors[x, y-1]
		if (y < NR)
			neighbors[x, y+1]

		for (pos in neighbors) {
			if (pos in visited || pos in total_risk)
				continue

			total_risk[pos] = total_risk[cur] + risk_level[pos]
			enqueue(total_risk[pos], pos)
		}

		visited[cur]
	}

	print total_risk[NF, NR]
}

function expand_map() {
	for(y = 1; y <= NR; y++)
	 for(x = 1; x <= NF; x++)
	  for(i = 0; i < 5; i++)
	   for(j = 0; j < 5; j++) {
		pos = (i*NF + x) SUBSEP (j*NR + y)
		risk_level[pos] = risk_level[x, y]+i+j
		if (risk_level[pos] > 9)
			risk_level[pos] -= 9
	   }

	NF *= 5
	NR *= 5
}

function enqueue(priority, item, prev) {
	items[priority, ++nitems[priority]] = item

	if (nitems[priority] > 1)
		return

	prev = ""
	while (queue[prev] != "" && priority > queue[prev])
		prev = queue[prev]

	queue[priority] = queue[prev]
	queue[prev] = priority
}

function dequeue(priority, ret) {
	priority = queue[""]
	if (priority == "")
		return ""

	ret = items[priority, nitems[priority]--]

	if (nitems[priority] == 0) {
		queue[""] = queue[priority]
		delete queue[priority]
	}

	return ret
}