Skip to content

Instantly share code, notes, and snippets.

@greenkey
Created April 13, 2014 20:48
Show Gist options
  • Save greenkey/10601753 to your computer and use it in GitHub Desktop.
Save greenkey/10601753 to your computer and use it in GitHub Desktop.
#!/usr/bin/python
"""Usage:
X.py < X.in > X.out
"""
################################################################################
# util functions
logging = False
globalCase = 0
def log(string="", case=0):
global globalCase
if logging:
if case > 0:
globalCase = case
string = "started case - %s" % string
print("Case #%d: %s" % (globalCase, string))
################################################################################
# problem functions
def solve(rows, cols, mines):
log("rows={}, cols={}, mines={}".format(rows, cols, mines))
board = ""
boardsize = rows * cols
freecells = boardsize - mines
# if one of the dimension is 1, it's always possible
if rows==1 or cols==1:
# then create the board
for r in range(rows):
board += "\n"
for c in range(cols):
# put mines since there are left
if mines > 0:
board += "*"
mines -= 1
else:
board += "."
# last character is wher I click
return board[:-1]+"c"
# special case: only one cell is free
if freecells == 1:
# then is a board full of mines
board = ("\n" + ("*"*cols))*rows
# except where I click
return board[:-1]+"c"
# if one of the dimension is 2, it's possible only if mines ar even
if (rows==2 or cols==2) and ((mines%2) == 1):
return "\nImpossible"
# special case, always impossible if 5, 3 or 2 cells free
if freecells in [5, 3, 2]:
return "\nImpossible"
# end of special cases, let's try to paint the board
# for every row
for r in range(rows):
if mines == 0:
# no mines left to paint, then put just dots
board += "\n" + ("."*cols)
elif rows-r == 2 and mines%2==1:
# oh-oh, two rows left and odd mines remaining, impossible!
return "\nImpossible"
else:
# all the other cases
x = mines/(rows-r) # this is just to not compute it everytime
if mines%(rows-r)==0 and x<(cols-2):
# if I can make a rectangle with the remaining mines, do it!
# but only if I can save the last two columns, so there is
# enough room for the click
# rectangle make it sure the click will expand to the maximum
# area possible, try to paint on paper!
board += "\n" + ("*"*x) + ("."*(cols-x))
mines -= x
# remember to decrease mines because next row it needs
# to be re-computed (I know, it's not a great thing)
else:
if mines == cols-1:
# This is a bad thing, because the one lonely cell avoids
# to expand the selection, leaving a cell uncovered.
# We need to prevent this!
if rows-r == 3:
# But if the remaining rows are three there is a special
# case when there are just 2 mines left, just try to
# paint it on paper.
if mines == 2:
return "\nImpossible"
else:
board += "\n" + ("*"*(mines-2)) + "..."
mines = 2
else:
# leave 2 colums for let the click expand properly
board += "\n" + ("*"*(mines-1)) + ".."
# there's only one mine left, but don't worry: there are
# more than 2 rows left
mines = 1
elif mines >= cols:
# Preserve Last 2 Cells of the last 2 rows.
# This is just to be sure that there's enough space for the
# click expasion.
plc = cols if rows-r>2 else cols-2
board += "\n" + ("*"*plc) + ("."*(cols-plc))
mines -= plc
else:
# Simply paint mines left and dots
board += "\n" + ("*"*mines) + ("."*(cols-mines))
mines = 0
# the click is always in the last cell
return board[:-1]+"c"
################################################################################
# main
if __name__ == '__main__':
import sys
r = sys.stdin.readline
cases = int(r())
for c in xrange(cases):
log(case=c+1)
(R, C, M) = map(int, r().split())
print 'Case #{}:{}'.format(c + 1, solve(R, C, M))
@greenkey
Copy link
Author

I wrote the majority of the code in the first minutes, but it took me some hours to discover a bug and then write lines 89..97

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment