#!/usr/bin/env python# Brick# Phil Bordelonimportosimportsys DEBUG = os.getenv("DEBUG", False)# Use a large number that is longer than any possible maximum# distance for Dijkstra's.BIG_NUMBER = 999defdijkstra(wall_dict, source, dest):# We're going to go through the nodes, finding the best-cost one each# step, ending when we get to the destination. We start with nothing# more than the source node. We prime the setup by starting with the# "start" (surprise!) and priming the list to visit with all nodes# adjacent to the start.visited_list = [source] to_visit_list = [(x, wall_dict[source]["connections"][x])forxinwall_dict[source]["connections"]] to_return= BIG_NUMBER done = Falsewhilenotdone:# Find the cheapest edge in the to_visit_list.short_edge = (None, BIG_NUMBER)foreleminto_visit_list:ifelem[1] < short_edge[1]: short_edge = elem# Visit it! Add it to the visited list, remove all other connections# to it in the to_visit_list, and add nodes it connects to that we# haven't gotten to yet, with proper weights.node_to_visit, cost = short_edge visited_list.append(node_to_visit)# Strip the to_visit_list of instances of this node ...to_visit_list = [xforxinto_visit_listifx[0] != node_to_visit]# Get the new entries ...ifDEBUG:repr(node_to_visit)# ... get all new places to visit (skipping already-visited places) ...new_visits = [xforxinwall_dict[node_to_visit]["connections"]ifxnotinvisited_list]# ... and add them to the to_visit_list. Also, bail if one of them is the dest.connections = wall_dict[node_to_visit]["connections"]forlocationinnew_visits:iflocation == dest:# We made it to the destination node, and know what the cost of# transit was.done = True to_return= connections[dest] + costelse: to_visit_list.append((location, cost + connections[location]))ifDEBUG:repr(to_visit_list)# Return the cost of transiting the grid.returnto_returndefbuildConnections(wall_dict, height, width):# In this lovely function, we build the connections between the various# bricks. If two squares are adjacent to each other and have the same# letter representation, they're part of the same brick, and so travel# between them is free. If the letter changes, though, that's a brick# "crossing", which counts as an actual "move."# First, we need to add the top and bottom "nodes." We keep them# out of the dictionary at first, then add them at the end.top = {"connections": {}} bottom = {"connections": {}}# Now, we set paths between all nodes. It costs 0 to move between# adjacent nodes that have the same letter, otherwise it costs 1.# This will incidentally give us the number of bricks necessary to# remove to get to the bottom of the wall, as you will never reenter# the same brick after leaving it (otherwise you could have stayed in# the brick in the first place, as all movement inside it costs 0.)forx, yinwall_dict: this_block = wall_dict[(x, y)]ifx == 0:# Top row. We only need to connect from the top to it, as it# will never be beneficial to go /back/ to the top from a lower# brick. We also need to make either this transit or the one# to the bottom cost something; I arbitrarily chose to make this# one cost.top["connections"][(x, y)] = 1ifx == height - 1:# Bottom row. Once again, it's not worth coming back /up/ from# the bottom, as that's the goal, so don't bother making connections# back up to this block.this_block["connections"]["bottom"] = 0else:# Check the block below. If it's the same letter, the cost is# zero; otherwise, it is one.below_block = wall_dict[(x + 1, y)]ifthis_block["letter"] == below_block["letter"]:# Make transit between this block and the one below it free.# We need to set the values in both directions, not just# down ... for reasons that are obvious if you consider how# devious us judges are.this_block["connections"][(x + 1, y)] = 0 below_block["connections"][(x, y)] = 0else:# Ya gotsta pay the price for this transit.this_block["connections"][(x + 1, y)] = 1 below_block["connections"][(x, y)] = 1# Do the same for the block to the right.ify < width - 1: right_block = wall_dict[(x, y + 1)]ifthis_block["letter"] == right_block["letter"]:# Free ride!this_block["connections"][(x, y + 1)] = 0 right_block["connections"][(x, y)] = 0else:# Not so much.this_block["connections"][(x, y + 1)] = 1 right_block["connections"][(x, y)] = 1# Finally, add the top and bottom to the dictionary.wall_dict["top"] = top wall_dict["bottom"] = bottomif"__main__" == __name__: dataset_count =int(sys.stdin.readline())fordataset_loopinrange(dataset_count):# Get the height and width ...height, width = [int(x)forxinsys.stdin.readline().strip().split()]# Then read the entire wall in.wall_dict = {}foriinrange(height): block_row = sys.stdin.readline().strip()iflen(block_row) != width: sys.exit("ERROR: Invalid width of line '%s' (should be %d)!" % (block_row, width))forjinrange(width):# Build the block for the big ol' table. We don't set up# connections between bits of bricks yet.wall_dict[(i, j)] = { "letter": block_row[j], "connections": {} }# Now that we've read the wall in, build the connections.buildConnections(wall_dict, height, width)# Lastly, Dijkstra!dijkstra(wall_dict, "top", "bottom")