fork download
copy 
  1. A,F='-0'
  2. R=range
  3. E=enumerate
  4. N=len
  5. M=[(1,0),(-1,0),(0,-1),(0,1)]
  6. def D(b):
  7.  for x,j in E(b):
  8.   for y,_ in E(j):
  9.    for X in R(x,N(b)):
  10.     for Y in R(y,N(b[0])):yield[(u,i)for u in R(x,X+1)for i in R(y,Y+1)]
  11. def r(b):
  12.  S={(x,y)for x,j in E(b)for y,_ in E(j)if F!=_};W={*S}
  13.  while S:
  14.   x,y=[(x,y)for x,y in S if A<b[x][y]][0];Z=(x,y);S-={Z};d,s={x:[y]},[Z];V=b[x][y];q=[Z]
  15.   while q:
  16.    x,y=q.pop(0)
  17.    for X,Y in M:
  18.     if(Z:=(J:=x+X,K:=y+Y))in S and b[J][K]in A+V:q+=Z,;S-={Z};d={**d,J:sorted(d.get(J,[])+[K])};s=s+[Z]
  19.    if all(b==d[min(d)]for b in d.values()):yield s
  20. def Z(B,s):
  21.  B=eval(str(B))
  22.  for x,y in s:B[x][y]=A
  23.  return B
  24. def f(b):
  25.  q,S=[(b,0)],[(0,b)];L=[i for i in D(b)if i];W=-1
  26.  while q:
  27.   B,c=q.pop()
  28.   if~-any({*i}-{A,F}for i in B):W=[min(W,c),c][W<0];continue
  29.   H=[*r(B)];V=lambda U:(2+c>W>=0)<all(C>c for C,u in S if u==U)
  30.   for i in H:
  31.    if V(U:=Z(B,i)):
  32.     q+=(U,c+1),;S+=(c,U),
  33.     if N({sum(A<B[x][y]for x,y in j)for j in H})==1:break
  34.   if V(U:=Z(B,max([i for i in L if N(T:={B[x][y]for x,y in i})-3<(F in T)<(N(T)==1or A in T)and A!=T],key=lambda X:sum(F!=B[x][y]>A for x,y in X)))):q+=(U,c+1),;S+=(c,U),
  35.  return W
  36.  
  37. s1 = """
  38. 1 1 1 1
  39. 1 2 2 2
  40. 1 2 3 3
  41. 1 2 3 4
  42. 1 2 3 4
  43. """
  44. s2 = """
  45. 1 1 2 2
  46. 1 1 2 2
  47. 3 3 1 3
  48. """
  49. s3 = """
  50. 1  2  3  4  5
  51. 6  7  8  9  10
  52. 11 12 13 14 15
  53. """
  54. s4 = """
  55. 3 3 3 3 3 3
  56. 3 2 2 2 2 3
  57. 3 2 1 1 2 3
  58. 3 2 1 1 2 3
  59. 3 2 2 2 2 3
  60. 3 3 3 3 3 3
  61. """
  62. s5 = """
  63. 1 1 1 1 1 1
  64. 1 2 2 2 2 1
  65. 1 2 0 0 2 1
  66. 1 2 0 0 2 1
  67. 1 2 2 2 2 1
  68. 1 1 1 1 1 1
  69. """
  70. s6 = """
  71. 0 0 0 0
  72. 0 0 0 0
  73. 0 0 0 0
  74. 0 0 0 0
  75. """
  76. s7 = """
  77. 1 1 1 1
  78. 1 3 3 1
  79. 2 3 3 2
  80. 2 2 2 4
  81. """
  82. def to_board(s):
  83. 	return [i.split()for i in filter(None, s.split('\n'))]
  84.  
  85.  
  86. print(f(to_board(s1)))
  87. print(f(to_board(s2))) #special test case
  88. print(f(to_board(s3)))
  89. print(f(to_board(s4)))
  90. print(f(to_board(s5)))
  91. print(f(to_board(s6)))
  92. print(f(to_board(s7)))
Success #stdin #stdout 1.03s 14116KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4
4
15
3
8
0
4
https://ideone.com/Pn4fzv
language:
Python 3 (python  3.12)
created:
23 hours 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!