Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import collections as c
- def bfs(row, col, grid, owner, pointId):
- dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
- queue = c.deque([((row, col), 0)])
- seen = set([(row, col)])
- while queue:
- currPos, dist = queue.popleft()
- grid[currPos[0]][currPos[1]] += dist
- for dir in dirs:
- nextPos = (currPos[0] + dir[0], currPos[1] + dir[1])
- if (nextPos[0] >= 0 and nextPos[0] < len(grid) and nextPos[1] >= 0 and nextPos[1] < len(grid[0])) and nextPos not in seen:
- seen.add(nextPos)
- queue.append((nextPos, dist + 1))
- owner[nextPos[0]][nextPos[1]] = pointId
- #for part 1, starting from a point and get the area of points it owns
- def bfsThroughPointsArea(row, col, grid, owner, pointId):
- dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
- area = 0
- queue = c.deque([(row, col)])
- seen = set([(row, col)])
- while queue:
- currPos = queue.popleft()
- area += 1
- for dir in dirs:
- nextPos = (currPos[0] + dir[0], currPos[1] + dir[1])
- if (nextPos[0] >= 0 and nextPos[0] < len(grid) and nextPos[1] >= 0 and nextPos[1] < len(grid[0])) and nextPos not in seen and owner[nextPos[0]][nextPos[1]] == pointId:
- seen.add(nextPos)
- queue.append(nextPos)
- #if you hit the edge, return 0
- elif nextPos[0] < 0 or nextPos[0] >= len(grid) or nextPos[1] < 0 or nextPos[1] >= len(grid[0]):
- print((row, col))
- return 0
- return area
- with open('input.txt') as f:
- distancesSoFar = [[]]
- allPoints = f.readlines()
- #go through points, get largest row and col
- rowSize = 0
- colSize = 0
- for p in allPoints:
- row, col = map(int, p.split(','))
- rowSize = max(rowSize, row)
- colSize = max(colSize, col)
- grid = [[0 for _ in range(colSize + 1)] for _ in range(rowSize + 1)]
- owners = [[-1 for _ in range(colSize + 1)] for _ in range(rowSize + 1)]
- largestArea = 0
- pId = 0
- for p in allPoints:
- row, col = map(int, p.split(','))
- bfs(row, col, grid, owners, pId)
- pId += 1
- pId = 0
- #for p in allPoints:
- #row, col = map(int, p.split(','))
- #largestArea = max(largestArea, bfsThroughPointsArea(row, col, grid, owners, pId))
- #pId += 1
- ans = 0
- for r in grid:
- s = ''
- for c in r:
- if c < 10000:
- ans += 1
- print(largestArea)
- print(ans)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement