Personal Website

My Web: MindEchoes.com

Friday, April 23, 2010

Programming Challenges: The Programming Contest Training Manual (2)

Cualquier bug encontrado o mejora que se pueda hacer al código, se agradecen los comentarios!

Problema 1.6.2: Minesweeper
   Have you ever played Minesweeper? This cute little game comes with a certain op-
erating system whose name we can’t remember. The goal of the game is to find where
all the mines are located within a M × N field.
   The game shows a number in a square which tells you how many mines there are
adjacent to that square. Each square has at most eight adjacent squares. The 4 × 4 field
on the left contains two mines, each represented by a “*” character. If we represent the
same field by the hint numbers described above, we end up with the field on the right:
                           *...             *100
                           ....             2210
                           .*..             1*10
                           ....             1110

Input
The input will consist of an arbitrary number of fields. The first line of each field
contains two integers n and m (0 < n, m ≤ 100) which stand for the number of lines
and columns of the field, respectively. Each of the next n lines contains exactly m
characters, representing the field.
  Safe squares are denoted by “.” and mine squares by “*,” both without the quotes.
The first field line where n = m = 0 represents the end of input and should not be
processed.

Output
For each field, print the message Field #x: on a line alone, where x stands for the
number of the field starting from 1. The next n lines should contain the field with the
“.” characters replaced by the number of mines adjacent to that square. There must
be an empty line between field outputs.

Sample Input
4 4
*...
....
.*..
....
3 5
**...
.....
.*...
0 0

Sample Output
Field #1:
*100
2210
1*10
1110

Field #2:
**100
33200
1*100

Solución:
import re

def main():
    f = open('input162', 'r')
    input = f.readlines()
    content = ''.join(line for line in input)
    pat = re.compile('(\d)')
    content = [c for c in pat.split(content) if c != '' and c != ' ']
    for i in range(len(content)/3):
        pos = i*3
        height = int(content[pos])
        width = int(content[pos+1])
        mines = content[pos+2]
        result = [m.replace('.', '0') for m in 
                    mines.split('\n') if m != '']
        resolve(height, width, result)
        if height > 0 and width > 0:
            print 'Field #' + str(i+1)
            for r in result:
                print r
            print '\n'
        
def resolve(height, width, result):
    mines = [[i, j] for i in range(height) 
        for j in range(width) if result[i][j] == '*']
    for m in mines:
        y = m[0]
        x = m[1]
        x -= 1
        sumar(result, x, y, height, width)
        y -= 1
        sumar(result, x, y, height, width)
        x += 1
        sumar(result, x, y, height, width)
        x += 1
        sumar(result, x, y, height, width)
        y += 1
        sumar(result, x, y, height, width)
        y += 1
        sumar(result, x, y, height, width)
        x -= 1
        sumar(result, x, y, height, width)
        x -= 1
        sumar(result, x, y, height, width)
        
def sumar(result, x, y, h, w):
    if -1 < x < w and -1 < y < h and result[y][x] != '*':
        result[y] = result[y][:x] + \
                str(int(result[y][x]) + 1) + result[y][x+1:]
        
    
if __name__ == '__main__':
    main()

No comments: