fork(1) download 
  1. M=[(1,0),(-1,0),(0,-1),(0,1)]
  2. E=enumerate
  3. def G(d):
  4.  q=[*d]
  5.  while q:
  6.   Q=[q.pop(0)];s=[*Q]
  7.   for x,y in Q:
  8.    for X,Y in M:
  9.     if(T:=(x+X,y+Y))in q and d[T]==d[(x,y)]:s+=T,;Q+=T,;q=[*{*q}-{T}]
  10.   yield s
  11. def f(b):
  12.  a,u=G({(x,y):v for x,r in E(b)for y,v in E(r)});q=[(u,*i)for i in M]
  13.  for b,x,y in q:
  14.   if[]==b:return 1
  15.   B,F=[],1
  16.   for X,Y in b:
  17.    if(T:=(x+X,y+Y))in a:F=0;break
  18.    B+=(T in u)*[T]
  19.   q+=F*[(B,x,y)]
  20.  
  21. s1 = """
  22. BBB
  23. BAA
  24. BBB
  25.  
  26. BA
  27.  
  28. A
  29. B
  30.  
  31. AB
  32. AB
  33.  
  34. AAA
  35. BBB
  36.  
  37. AAAAB
  38. ABBBB
  39.  
  40. ABBA
  41. ABBA
  42. AAAA
  43.  
  44. AAAAAABBBBBBBBB
  45. AABBBBBBBBBBBBB
  46. AAAAAAAAAABBBBB
  47. AABBBBBBBBBBBBB
  48. AAAAAAAAAAAAAAB
  49.  
  50. AAAAAAAAAAAA
  51. ABABABABABAB
  52. BBBBBBBBBBBB
  53.  
  54. BAAAAABB
  55. BBAAABBB
  56. BBBABBBB
  57. BBBABBBB
  58. BBBABBBB
  59. BBBBBBBB
  60. BBBBBBBB
  61.  
  62. AAA
  63. BAA
  64. AAA
  65. """
  66. s2 = """
  67. BBBB
  68. BAAB
  69. BABB
  70.  
  71. BBBB
  72. BAAB
  73. AABB
  74.  
  75. BBBBBBB
  76. BBBBBAB
  77. AAAAAAB
  78. BBBBBBB
  79.  
  80. BAAA
  81. BABA
  82. BBBA
  83. AABA
  84. AAAA
  85.  
  86. AAAAAAA
  87. ABBBBBA
  88. AAAAABA
  89. BBBBBBA
  90.  
  91. BAAAAABB
  92. BBAAABBB
  93. BBBABBBB
  94. BBBABBBB
  95. BBBAABBB
  96. BBBBBBBB
  97. BBBBBBBB
  98.  
  99. AAA
  100. ABA
  101. BBA
  102. ABA
  103. AAA
  104. """
  105.  
  106. def to_board(s):
  107. 	return [[*i]for i in filter(None, s.split('\n'))]
  108.  
  109.  
  110. for a, b in [(s1, 1), (s2, None)]:
  111. 	for j in a.split('\n\n'):
  112. 		assert f(to_board(j))==b
  113.  
  114. print('tests passed')
Success #stdin #stdout 0.09s 14128KB
comments (?)
stdin 
Standard input is empty
stdout 
tests passed
https://ideone.com/A7macB
language:
Python 3 (python  3.12)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!