Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from disjoint_set import DisjointSet
- import sys
- def addpt(pt1, pt2):
- return (pt1[0] + pt2[0], pt1[1] + pt2[1])
- def inrange(pt, ysize, xsize):
- return pt[0] >= 0 and pt[1] >=0 and pt[0] < ysize and pt[1] < xsize
- def badwalls(w):
- if len(w) < 2:
- return False
- if len(w) > 2:
- return True
- if "U" in w and "R" in w:
- return False
- if "D" in w and "L" in w:
- return False
- return True
- DDIRS=((1, 0), (1, 1), (0,1), (-1, 1), (-1,0), (-1, -1), (0,-1), (1, -1))
- xsize = 71
- ysize = 71
- maxb = 1024
- if len(sys.argv) > 1 and sys.argv[1] == 'x':
- ysize = 7
- xsize = 7
- maxb = 12
- if len(sys.argv) > 1 and sys.argv[1] == 'b':
- ysize = 213
- xsize = 213
- maxb = 1024
- walls = dict()
- corrupt = set()
- ds = DisjointSet()
- for l in sys.stdin:
- x,y = [int(x) for x in l.split(",")]
- wallset = set()
- if x == 0:
- wallset.add("L")
- if y == 0:
- wallset.add("U")
- if x == xsize - 1:
- wallset.add("R")
- if y == ysize - 1:
- wallset.add("D")
- pt = (y,x)
- corrupt.add(pt)
- rep = ds.find(pt)
- walls[rep] = wallset
- for d in DDIRS:
- tp = addpt(pt, d)
- if inrange(tp, ysize, xsize) and tp in corrupt:
- otherrep = ds.find(tp)
- #print(pt, tp, otherrep)
- wallset = walls[otherrep].union(walls[rep])
- if badwalls(wallset):
- print(str(pt[1])+","+str(pt[0]))
- exit(0)
- ds.union(rep, otherrep)
- newrep = ds.find(rep)
- #print(pt, tp, otherrep, newrep)
- if newrep != otherrep:
- del walls[otherrep]
- if newrep != rep:
- del walls[rep]
- rep = newrep
- walls[rep] = wallset
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement