#!/usr/bin/env python# A solution for Influence, written in Python.# by Phil Bordelon# 0 1 2# . . . 0# . . . 1# . . . 2## (1,1) is adjacent to (1,0), (1,2), (0,1), (2,1) (the obvious ones),# plus (2,0) and (0,2) (the less-obvious ones).importosimportsys# This number should be larger than any possible distance in the problem.MAX_DISTANCE = 999# This number should be the maximum size of the grid.MAX_SIZE = 26# Debug?DEBUG = os.getenv("DEBUG", False)defdistance(x1, y1, x2, y2):# Calculate the raw numeric differences. We also need the magnitudes# of the differences, for the "less-obvious" adjacency math.x_delta = x2 - x1 y_delta = y2 - y1 x_delta_mag =abs(x_delta) y_delta_mag =abs(y_delta)# First, do the math if it's the less-obvious adjacencies, which only# occurs if the two deltas are going in different directions.if(x_delta < 0andy_delta > 0)or(x_delta > 0andy_delta < 0):# The distance is the number of steps diagonally (taken from# both numbers), plus the length of the larger leg. So the# math can be done as short leg + (long leg - short leg).ifx_delta_mag < y_delta_mag: distance = x_delta_mag + (y_delta_mag - x_delta_mag)else: distance = y_delta_mag + (x_delta_mag - y_delta_mag)else:# Boring distance math.distance = x_delta_mag + y_delta_magreturndistancedefprecalcGrid():# We precalculate the distances for every cell from every other cell,# because this makes the actual solution phase of the problem a series# of calls into look-up tables.grid = {}forx1inrange(MAX_SIZE):fory1inrange(MAX_SIZE): new_location = {}forx2inrange(MAX_SIZE):fory2inrange(MAX_SIZE): new_location[(x2,y2)] =distance(x1, y1, x2, y2) grid[(x1,y1)] = new_locationreturngriddefdrawBoard(grid, size):# This is a quick little debug function that draws a representation of the# board.lookup = (".", "!", "@", "#", "$")foriinrange(size):forxinrange(i):forjinrange(size):ifgrid[(i,j)]["piece"] > 0:else:defcalculateScoreAndUpdateGrid(grid):# As the rather verbose function title states, this function calculates the# score for various players given a particular board layout, along with# updating the grid's knowledge of the closest pieces to each location,# which is used for when we try to place new pieces. Yes, it's bad form to# do both of these things in the same function, but it makes sense to not# run through the board twice, and this /is/ programming contest code.# Easy part first; start scores out as the count of pieces.foriinrange(4): grid[i + 1]["score"] = grid[i + 1]["count"]# Loop through the empty spaces on the grid.fori, jingrid["emptylist"]:# For each location, find the owner, if any, and the distance to# said closest piece. This is easy. We loop over every pieces on the# board and find the closest ones. If there's more than one player# with the closest pieces, no one owns it.closest_owner = 0 closest_distance = MAX_DISTANCEfork, l, owneringrid["piecelist"]: distance = grid[(i,j)][(k,l)]ifdistance < closest_distance:# Clear new winner. Record.closest_distance = distance closest_owner = ownerelifdistance == closest_distance:# If two players are closest, we need to set the owner to# zero. If we've already determined it's contested, it# needs to stay that way.ifclosest_owner > 0andowner != closest_owner:# The piece is contested.closest_owner = 0# Save the closest distance and closest owner.grid[(i,j)]["closest_distance"] = closest_distance grid[(i,j)]["closest_owner"] = closest_owner# If the closest owner is an actual player (as opposed to the contested# value), increment their score.ifclosest_owner: grid[closest_owner]["score"] += 1# Return the updated grid.returngriddefsetupGrid(grid, size):# Here we set up the grid for a particular data set, clearing out scores# and reading in the pieces and empty spaces from the input.# First, clear out the piece counts for each player.grid[1] = {"count": 0, "score": 0} grid[2] = {"count": 0, "score": 0} grid[3] = {"count": 0, "score": 0} grid[4] = {"count": 0, "score": 0}# Also clear out the lists of pieces and empty locations.grid["piecelist"] = [] grid["emptylist"] = []# Now, read in each piece and put it in the grid, incrementing counts# as necessary.foriinrange(size): line = sys.stdin.readline().strip()# Get the actual characters from the line, whitespace-free.pieces_in_line = [xforxinline.split()iflen(x) > 0]# Mild error checking.iflen(pieces_in_line) != size: sys.exit("ERROR: Wrong number of pieces in line with piece setup %s!" % line)# Loop through each piece in this line.forjinrange(len(pieces_in_line)): piece = pieces_in_line[j]ifpiece == ".":# An empty space. Append this location to the empty list, and set# its owner to no one.grid[(i,j)]["piece"] = 0 grid["emptylist"].append((i,j))elifpiece == "!":# A piece for the first player. Add this location to the piece# list, increment their count of pieces by one, and set its owner# to the first player.grid[(i,j)]["piece"] = 1 grid[1]["count"] += 1 grid["piecelist"].append((i,j, 1))elifpiece == "@":# The second player ...grid[(i,j)]["piece"] = 2 grid[2]["count"] += 1 grid["piecelist"].append((i,j, 2))elifpiece == "#":# ... the third ...grid[(i,j)]["piece"] = 3 grid[3]["count"] += 1 grid["piecelist"].append((i,j, 3))elifpiece == "$":# ... and the fourth.grid[(i,j)]["piece"] = 4 grid[4]["count"] += 1 grid["piecelist"].append((i,j, 4))# Now that we've read every piece in the grid, calculate each empty# space's shortest distance to a piece and the current score.grid =calculateScoreAndUpdateGrid(grid)# Return.returngriddefbestScore(grid, size, player):# Here we determine the best possible score for a player if they have# one more move.# The score can never be worse than the score the player already has.score = grid[player]["score"] best_additional_points = 0ifDEBUG: best_spot = "NONE"# Now, try putting a piece for this player in each empty location.fori, jingrid["emptylist"]: additional_points = 0# Check every /other/ empty location to see if this spot is closer# to it than any other player's piece.fork, lingrid["emptylist"]: distance = grid[(i,j)][(k,l)]ifdistance < grid[(k,l)]["closest_distance"]:# Well, this is indeed closer than any other piece, but we# can't count the location twice if the player already /had/# the closest piece to this location.ifplayer != grid[(k,l)]["closest_owner"]: additional_points += 1# Record this if it's the best number of additional points we've# found.ifadditional_points > best_additional_points: best_additional_points = additional_pointsifDEBUG: best_spot = (i,j)ifDEBUG:repr(best_spot)# Return the best number of points we've found for this player.returnscore + best_additional_pointsif"__main__" == __name__:# Precalculate the adjacencies for the grid.grid =precalcGrid() dataset_count =int(sys.stdin.readline())fordataset_loopinrange(dataset_count):# Get the count of players and the size of the board.player_count =int(sys.stdin.readline()) size =int(sys.stdin.readline())# Read the board in, populating our representation with distances# to the nearest pieces.grid =setupGrid(grid, size)ifDEBUG:drawBoard(grid, size)# Lastly, find the best new spots for pieces for each player.foriinrange(player_count):bestScore(grid, size, i + 1)