none working gcj minesweeper

code.py

"""
This code is meant to solve the Google Code Jam Mine Sweeper Master, but doesn't, and I have no idea why.
I'll describe what it does. In all these examples, r and c will be 5, unless otherwise noted

if m is exactly (r*c)-1, you can just click anywhere,
and put mines everywhere else. The cell you clicked will show an 8, and you win.

if r or c is equal to 1, check if there are at least 2 open spaces.
Now, just construct a line, with the given number of mines at the top, or the left, for a column or row respectively,
and the click at the bottom or right.

In any other case if there are less than 4 open spaces, it's impossible.
Start filling the grid with mines from left to right, and from top to bottom, and click in the bottom right.

let's say m=8:

Case #X:
*****
***..
.....
.....
....c

This works great, but you need to make sure that you don't have a bottom row with 1 empty spot on the right.
Let's say m=9. In this output, 'n' means that a number other than 0 will appear in that cell, meaning that it won't open its neighbors,
and 'x' is an unopened cell

Case #X:
*****
****x
nnnnn
.....
....c

The solution is to move the last mine to the next line:

Case #X:
*****
***nn
*nnn.
nn...
....c

We do this untill we've filled up all the lines except the last two lines.

If we have any mines left to put down, we put them down on the bottom 2 lines in pairs,
so for m=17, it looks like this:

*****
*****
*****
*nnnn
*n..c

and for m=21, it looks like this:

Case #X:
*****
*****
*****
***nn
***nc

This means that we can't have an odd number of mines left to lay down in the bottom two rows,
because in that case, we have a similar problem to the row with one open spot. Let's see what m=18 looks like:

Case #X:
*****
*****
*****
**nnn
*xn.c

The numbers neighboring the unpaired mine block the second cell on the bottom row from being revealed.

What check am I missing?

"""


from mpmath import *
mp.dps = 20
import sys
inp = open("in.txt")
out = open("out.txt","w+")
sys.stdout = out

t = int(inp.readline())

def print_case(case, result):
	print "Case #%d: %s" % (case, str(result))

def handle_one_open_spot(r, c, m):
	#just make a field of r rows and c columns, filled with mines
	field = r*(c*"*"+"\n")
	#make the last mine into a "c". It's -2 because the final character is a newline.
	field = field[:-2] + "c"
	print_case(tc+1,"\n"+field)

def handle_single_row(r, c, m):
	if m <= c-2: #we need 2 open spots, one for the click and one next to the clicks. If there's only one, handle_one_open_spot handles it
		print_case(tc+1,"\n"+"*"*m + "."*(c-m-1)+"c")
	else:
		print_case(tc+1,"\nImpossible")

def handle_single_column(r, c, m):
	if m <= r-2:
		print_case(tc+1,"\n*"*m+"\n."*(r-m-1) + "\nc")
	else:
		print_case(tc+1,"\nImpossible")

def make_empty_field(r, c):
	f = []
	for i in xrange(r):
		f.append(["."]*c)
	
	return f

def fill_top_rows(r, c, m, f):
	"""Fills all the rows except the bottom 2 ones with mines"""
	for i in xrange(r-2): 
		for j in xrange(c):
			if m == 1 and j == c-2: #make sure that there's no single empty cell at the end of a row
				break
			f[i][j] = "*"
			m -= 1
			if m == 0:
				return 0
	
	return m #the remaining mines

def fill_bottom_rows(r, c, m, f):
	if m == 0:
		return True #no mines to lay down, we're done!
	
	if m %2 != 0:
		return False #we can't have an uneven number of mines in the bottom 2 rows
	
	for i in xrange(c-2):
		if m >1:
			f[-2][i] = "*"
			f[-1][i] = "*"
			m -= 2
	
	return True

def handle_matrix(r, c, m):
	if m > (r*c)-4:
		print_case(tc+1,"\nImpossible")
	else:
		f = make_empty_field(r, c)
		f[-1][-1] = "c" #click in the bottom right
		
		remaining = fill_top_rows(r, c, m, f)
		
		result = fill_bottom_rows(r, c, remaining, f)
		
		if result:
			print_case(tc+1,"\n"+"\n".join(["".join(x) for x in f]))
		else:
			print_case(tc+1,"\nImpossible")

for tc in xrange(t):
	r, c, m = [int(x) for x in inp.readline().split()]
	if m == r*c-1:
		handle_one_open_spot(r, c, m)
		continue
	if r == 1:
		handle_single_row(r, c, m)
		continue
	if c == 1:
		handle_single_column(r, c, m)
		continue
	handle_matrix(r, c, m)

example input

5
5 5 23
3 1 1
2 2 1
4 7 3
10 10 82

example output

Case #1: 
Impossible
Case #2: 
*
.
c
Case #3: 
Impossible
Case #4: 
***....
.......
.......
......c
Case #5: 
**********
**********
**********
**********
**********
**********
**********
**********
*.........
*........c

small input

225
1 4 0
3 4 11
3 5 9
5 4 17
3 3 5
4 5 7
3 5 11
4 4 7
1 5 2
5 5 23
3 5 12
4 4 12
3 3 1
4 3 10
5 3 13
5 3 9
4 4 10
4 3 9
3 1 1
2 2 3
5 4 15
3 5 2
4 3 1
5 4 12
5 4 16
2 4 0
3 4 0
4 4 1
3 2 2
5 4 8
5 4 2
5 4 7
2 3 5
5 5 10
5 4 4
3 5 14
3 4 8
4 2 6
4 5 2
4 5 17
3 3 8
2 4 5
5 4 5
4 5 16
3 5 4
4 1 1
4 5 12
4 3 0
3 5 6
2 5 8
3 5 7
4 5 13
2 4 1
5 5 22
5 5 0
4 2 3
4 4 11
5 4 13
2 3 1
2 5 2
4 5 19
2 5 9
2 4 3
2 4 7
4 1 0
3 2 3
5 3 8
4 4 8
5 5 13
2 5 6
2 4 4
5 1 2
4 4 2
3 1 0
5 5 3
3 5 1
5 4 9
2 5 7
2 2 1
1 5 3
4 4 13
4 4 0
3 5 13
4 1 2
3 2 1
4 4 9
5 4 1
3 5 10
1 3 2
5 4 11
2 1 1
5 5 17
5 2 4
4 5 18
4 3 3
5 4 3
5 1 3
5 4 19
5 5 14
4 3 6
4 3 2
4 3 4
5 2 7
5 4 10
5 3 3
5 4 18
4 5 0
3 5 3
3 4 3
4 3 5
3 4 1
1 2 0
5 5 19
5 5 5
5 2 9
5 5 2
2 3 0
5 5 8
5 2 5
2 4 6
4 4 3
2 1 0
5 2 6
4 4 14
1 4 2
4 2 7
4 3 8
3 2 5
5 3 14
4 2 1
1 4 1
1 1 0
2 5 5
4 2 0
2 5 4
5 5 1
3 3 4
3 5 5
3 3 7
3 3 3
3 3 0
3 1 2
4 5 14
5 3 0
3 4 10
5 3 5
5 2 3
5 4 6
4 4 5
5 1 1
1 4 3
3 3 6
5 2 2
5 2 1
5 4 14
5 5 7
5 5 4
4 5 5
4 5 6
4 4 4
1 5 1
4 1 3
4 2 4
2 2 2
2 5 3
1 3 1
5 3 4
3 4 4
5 3 10
2 5 0
5 1 0
2 4 2
4 5 8
1 5 4
1 2 1
5 4 0
5 5 24
3 4 7
5 3 1
4 4 6
5 3 7
5 5 21
2 3 3
4 3 11
5 5 6
4 4 15
5 5 11
4 5 1
3 5 8
4 5 3
3 2 4
5 2 0
5 5 9
5 1 4
1 5 0
4 2 2
4 2 5
5 3 12
3 4 9
2 3 2
4 5 10
3 4 6
4 5 11
4 5 4
2 5 1
5 5 20
4 3 7
5 5 12
5 3 2
1 3 0
4 5 15
3 4 2
5 5 18
4 5 9
3 5 0
5 5 15
3 2 0
5 3 6
5 2 8
2 3 4
3 4 5
5 3 11
5 5 16
3 3 2
2 2 0

small output

Case #1: 
...c
Case #2: 
****
****
***c
Case #3: 
*****
**...
**..c
Case #4: 
Impossible
Case #5: 
***
*..
*.c
Case #6: 
*****
**...
.....
....c
Case #7: 
*****
***..
***.c
Case #8: 
Impossible
Case #9: 
**..c
Case #10: 
Impossible
Case #11: 
Impossible
Case #12: 
****
****
**..
**.c
Case #13: 
*..
...
..c
Case #14: 
Impossible
Case #15: 
Impossible
Case #16: 
***
***
***
...
..c
Case #17: 
****
****
*...
*..c
Case #18: 
Impossible
Case #19: 
*
.
c
Case #20: 
**
*c
Case #21: 
Impossible
Case #22: 
**...
.....
....c
Case #23: 
*..
...
...
..c
Case #24: 
****
****
****
....
...c
Case #25: 
****
****
****
**..
**.c
Case #26: 
....
...c
Case #27: 
****
....
...c
Case #28: 
*...
....
....
...c
Case #29: 
**
..
.c
Case #30: 
****
****
....
....
...c
Case #31: 
**..
....
....
....
...c
Case #32: 
****
**..
*...
....
...c
Case #33: 
***
**c
Case #34: 
*****
*****
.....
.....
....c
Case #35: 
****
....
....
....
...c
Case #36: 
*****
*****
****c
Case #37: 
****
**..
**.c
Case #38: 
Impossible
Case #39: 
**...
.....
.....
....c
Case #40: 
Impossible
Case #41: 
***
***
**c
Case #42: 
Impossible
Case #43: 
****
*...
....
....
...c
Case #44: 
*****
*****
***..
***.c
Case #45: 
Impossible
Case #46: 
*
.
.
c
Case #47: 
*****
*****
*....
*...c
Case #48: 
***
***
...
..c
Case #49: 
Impossible
Case #50: 
Impossible
Case #51: 
*****
*....
*...c
Case #52: 
Impossible
Case #53: 
Impossible
Case #54: 
Impossible
Case #55: 
Impossible
Case #56: 
Impossible
Case #57: 
Impossible
Case #58: 
Impossible
Case #59: 
Impossible
Case #60: 
*....
*...c
Case #61: 
*****
*****
*****
****c
Case #62: 
*****
****c
Case #63: 
Impossible
Case #64: 
****
***c
Case #65: 
.
.
.
c
Case #66: 
Impossible
Case #67: 
Impossible
Case #68: 
****
****
....
...c
Case #69: 
*****
*****
***..
.....
....c
Case #70: 
***..
***.c
Case #71: 
**..
**.c
Case #72: 
*
*
.
.
c
Case #73: 
**..
....
....
...c
Case #74: 
.
.
c
Case #75: 
***..
.....
.....
.....
....c
Case #76: 
*....
.....
....c
Case #77: 
****
****
*...
....
...c
Case #78: 
Impossible
Case #79: 
Impossible
Case #80: 
***.c
Case #81: 
Impossible
Case #82: 
****
****
....
...c
Case #83: 
Impossible
Case #84: 
*
*
.
c
Case #85: 
Impossible
Case #86: 
Impossible
Case #87: 
*...
....
....
....
...c
Case #88: 
Impossible
Case #89: 
**c
Case #90: 
Impossible
Case #91: 
*
c
Case #92: 
*****
*****
*****
*....
*...c
Case #93: 
**
**
..
..
.c
Case #94: 
Impossible
Case #95: 
***
...
...
..c
Case #96: 
**..
*...
....
....
...c
Case #97: 
*
*
*
.
c
Case #98: 
****
****
****
****
***c
Case #99: 
Impossible
Case #100: 
***
***
...
..c
Case #101: 
*..
*..
...
..c
Case #102: 
***
*..
...
..c
Case #103: 
Impossible
Case #104: 
****
****
**..
....
...c
Case #105: 
***
...
...
...
..c
Case #106: 
Impossible
Case #107: 
*****
*****
.....
....c
Case #108: 
***..
.....
....c
Case #109: 
Impossible
Case #110: 
Impossible
Case #111: 
*...
....
...c
Case #112: 
.c
Case #113: 
*****
*****
*****
**...
**..c
Case #114: 
*****
.....
.....
.....
....c
Case #115: 
**
**
**
**
*c
Case #116: 
**...
.....
.....
.....
....c
Case #117: 
...
..c
Case #118: 
*****
***..
.....
.....
....c
Case #119: 
Impossible
Case #120: 
Impossible
Case #121: 
**..
*...
....
...c
Case #122: 
.
c
Case #123: 
**
**
**
..
.c
Case #124: 
Impossible
Case #125: 
**.c
Case #126: 
**
**
**
*c
Case #127: 
***
***
*..
*.c
Case #128: 
**
**
*c
Case #129: 
***
***
***
***
**c
Case #130: 
Impossible
Case #131: 
*..c
Case #132: 
c
Case #133: 
Impossible
Case #134: 
**
**
..
.c
Case #135: 
**...
**..c
Case #136: 
*....
.....
.....
.....
....c
Case #137: 
Impossible
Case #138: 
*****
.....
....c
Case #139: 
Impossible
Case #140: 
***
...
..c
Case #141: 
Impossible
Case #142: 
*
*
c
Case #143: 
*****
*****
**...
**..c
Case #144: 
Impossible
Case #145: 
Impossible
Case #146: 
***
*..
*..
...
..c
Case #147: 
Impossible
Case #148: 
****
**..
....
....
...c
Case #149: 
****
*...
....
...c
Case #150: 
*
.
.
.
c
Case #151: 
***c
Case #152: 
Impossible
Case #153: 
**
..
..
..
.c
Case #154: 
Impossible
Case #155: 
****
****
****
*...
*..c
Case #156: 
*****
**...
.....
.....
....c
Case #157: 
***..
*....
.....
.....
....c
Case #158: 
*****
.....
.....
....c
Case #159: 
*****
*....
.....
....c
Case #160: 
****
....
....
...c
Case #161: 
*...c
Case #162: 
*
*
*
c
Case #163: 
**
**
..
.c
Case #164: 
Impossible
Case #165: 
Impossible
Case #166: 
*.c
Case #167: 
***
*..
...
...
..c
Case #168: 
****
....
...c
Case #169: 
Impossible
Case #170: 
.....
....c
Case #171: 
.
.
.
.
c
Case #172: 
*...
*..c
Case #173: 
*****
***..
.....
....c
Case #174: 
****c
Case #175: 
*c
Case #176: 
****
****
****
....
...c
Case #177: 
*****
*****
*****
*****
****c
Case #178: 
Impossible
Case #179: 
*..
...
...
...
..c
Case #180: 
****
**..
....
...c
Case #181: 
***
***
*..
...
..c
Case #182: 
*****
*****
*****
***..
***.c
Case #183: 
Impossible
Case #184: 
***
***
***
**c
Case #185: 
*****
*....
.....
.....
....c
Case #186: 
****
****
****
***c
Case #187: 
*****
*****
*....
.....
....c
Case #188: 
*....
.....
.....
....c
Case #189: 
Impossible
Case #190: 
***..
.....
.....
....c
Case #191: 
Impossible
Case #192: 
**
**
**
..
.c
Case #193: 
*****
***..
*....
.....
....c
Case #194: 
*
*
*
*
c
Case #195: 
....c
Case #196: 
**
..
..
.c
Case #197: 
Impossible
Case #198: 
Impossible
Case #199: 
Impossible
Case #200: 
*..
*.c
Case #201: 
*****
*****
.....
....c
Case #202: 
****
*...
*..c
Case #203: 
Impossible
Case #204: 
***..
*....
.....
....c
Case #205: 
Impossible
Case #206: 
Impossible
Case #207: 
Impossible
Case #208: 
*****
*****
**...
.....
....c
Case #209: 
*..
*..
...
...
..c
Case #210: 
..c
Case #211: 
Impossible
Case #212: 
**..
....
...c
Case #213: 
Impossible
Case #214: 
Impossible
Case #215: 
Impossible
Case #216: 
*****
*****
*****
.....
....c
Case #217: 
**
..
.c
Case #218: 
***
***
...
...
..c
Case #219: 
Impossible
Case #220: 
Impossible
Case #221: 
Impossible
Case #222: 
***
***
***
*..
*.c
Case #223: 
Impossible
Case #224: 
Impossible
Case #225: 
..
.c