Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
breadth first search solution in Clear category for Safe Coasts by 1-more
def finish_map(region):
neighbours = ((-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1))
directions = ((-1,0), (0,-1), (0,1), (1,0))
region = [list(row.replace('.', 'S')) for row in region]
is_inside = lambda row, col: 0 <= row < len(region) and 0 <= col < len(region[0])
queue = [(r,c) for r,row in enumerate(region) for c,col in enumerate(row) if col=='D']
while queue:
row, col = queue.pop(0)
for dr, dc in directions:
r, c = row + dr, col + dc
if is_inside(r, c) and region[r][c] != 'D' and all(
region[r + ddr][c + ddc] != 'X' for ddr, ddc in neighbours
if is_inside(r + ddr, c + ddc)
):
region[r][c] = 'D'
queue.append((r, c))
return [''.join(row) for row in region]
if __name__ == '__main__':
#These "asserts" using only for self-checking and not necessary for auto-testing
assert isinstance(finish_map(("D..", "...", "...")), (list, tuple)), "List or tuple"
assert list(finish_map(("D..XX.....",
"...X......",
".......X..",
".......X..",
"...X...X..",
"...XXXXX..",
"X.........",
"..X.......",
"..........",
"D...X....D"))) == ["DDSXXSDDDD",
"DDSXSSSSSD",
"DDSSSSSXSD",
"DDSSSSSXSD",
"DDSXSSSXSD",
"SSSXXXXXSD",
"XSSSSSSSSD",
"SSXSDDDDDD",
"DSSSSSDDDD",
"DDDSXSDDDD"], "Example"
assert list(finish_map(("........",
"........",
"X.X..X.X",
"........",
"...D....",
"........",
"X.X..X.X",
"........",
"........",))) == ["SSSSSSSS",
"SSSSSSSS",
"XSXSSXSX",
"SSSSSSSS",
"DDDDDDDD",
"SSSSSSSS",
'XSXSSXSX',
"SSSSSSSS",
"SSSSSSSS"], "Walls"
April 10, 2018
Comments:
