Advertisement
Guest User

Untitled

a guest
Dec 18th, 2024
20
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.78 KB | None | 0 0
  1. from disjoint_set import DisjointSet
  2. import sys
  3.  
  4. def addpt(pt1, pt2):
  5. return (pt1[0] + pt2[0], pt1[1] + pt2[1])
  6.  
  7. def inrange(pt, ysize, xsize):
  8. return pt[0] >= 0 and pt[1] >=0 and pt[0] < ysize and pt[1] < xsize
  9.  
  10. def badwalls(w):
  11. if len(w) < 2:
  12. return False
  13. if len(w) > 2:
  14. return True
  15. if "U" in w and "R" in w:
  16. return False
  17. if "D" in w and "L" in w:
  18. return False
  19. return True
  20.  
  21. DDIRS=((1, 0), (1, 1), (0,1), (-1, 1), (-1,0), (-1, -1), (0,-1), (1, -1))
  22. xsize = 71
  23. ysize = 71
  24. maxb = 1024
  25. if len(sys.argv) > 1 and sys.argv[1] == 'x':
  26. ysize = 7
  27. xsize = 7
  28. maxb = 12
  29. if len(sys.argv) > 1 and sys.argv[1] == 'b':
  30. ysize = 213
  31. xsize = 213
  32. maxb = 1024
  33.  
  34. walls = dict()
  35. corrupt = set()
  36. ds = DisjointSet()
  37. for l in sys.stdin:
  38. x,y = [int(x) for x in l.split(",")]
  39. wallset = set()
  40. if x == 0:
  41. wallset.add("L")
  42. if y == 0:
  43. wallset.add("U")
  44. if x == xsize - 1:
  45. wallset.add("R")
  46. if y == ysize - 1:
  47. wallset.add("D")
  48. pt = (y,x)
  49. corrupt.add(pt)
  50. rep = ds.find(pt)
  51. walls[rep] = wallset
  52. for d in DDIRS:
  53. tp = addpt(pt, d)
  54. if inrange(tp, ysize, xsize) and tp in corrupt:
  55. otherrep = ds.find(tp)
  56. #print(pt, tp, otherrep)
  57. wallset = walls[otherrep].union(walls[rep])
  58. if badwalls(wallset):
  59. print(str(pt[1])+","+str(pt[0]))
  60. exit(0)
  61. ds.union(rep, otherrep)
  62. newrep = ds.find(rep)
  63. #print(pt, tp, otherrep, newrep)
  64. if newrep != otherrep:
  65. del walls[otherrep]
  66. if newrep != rep:
  67. del walls[rep]
  68. rep = newrep
  69. walls[rep] = wallset
  70.  
  71.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement