fork download
  1.  
  2. # 20 21 22 23 24
  3. # 15 16 17 18 19
  4. # 10 11 12 13 14
  5. # 05 06 07 08 09
  6. # 00 01 02 03 04
  7.  
  8. # 0
  9. # 3 1
  10. # 2
  11.  
  12. def read_field():
  13. return sum([int(input().strip()[::-1].replace('R','1').replace('W','0'),2)<<(i*5)for i in range(4,-1,-1)])
  14. def print_field(field):
  15. print(hex(field))
  16. for i in range(4,-1,-1):
  17. print(*['WR'[field>>i*5+j&1]for j in range(5)])
  18.  
  19. def new_state(pos,went,field):
  20. return pos<<27|went<<25|field
  21. def get_pos(state):
  22. return state>>27
  23. def get_went(state):
  24. return state>>25&3
  25. def get_field(state):
  26. return state&(1<<25)-1
  27. def go_left(state):
  28. pos=get_pos(state)
  29. return new_state(pos-1,3,1<<pos-1^get_field(state)) if get_went(state)!=1 and pos%5>0 else -1
  30. def go_right(state):
  31. pos=get_pos(state)
  32. return new_state(pos+1,1,1<<pos+1^get_field(state)) if get_went(state)!=3 and pos%5<4 else -1
  33. def go_up(state):
  34. pos=get_pos(state)
  35. return new_state(pos+5,0,1<<pos+5^get_field(state)) if get_went(state)!=2 and pos//5<4 else -1
  36. def go_down(state):
  37. pos=get_pos(state)
  38. return new_state(pos-5,2,1<<pos-5^get_field(state)) if get_went(state)!=0 and pos//5>0 else -1
  39.  
  40.  
  41. field=read_field()
  42. print_field(field)
  43.  
  44. first=new_state(0,0,field^1)
  45. stateset=set()
  46. stateset.add(first)
  47.  
  48. steps=[first]
  49.  
  50. for i in range(17):
  51. print('step',i+1,':',len(steps))
  52. temp=[]
  53. for current in steps:
  54. for func in [go_left,go_right,go_up,go_down]:
  55. step=func(current)
  56. if step!=-1 and not step in stateset:
  57. stateset.add(step)
  58. temp.append(step)
  59. steps=temp
  60.  
  61. print('step',18,':',len(steps))
Success #stdin #stdout 2.6s 38120KB
stdin
RWWWR
WRWWW
RWRWW
RWWRW
WRRWR
stdout
0x1111536
R W W W R
W R W W W
R W R W W
R W W R W
W R R W R
step 1 : 1
step 2 : 2
step 3 : 4
step 4 : 10
step 5 : 26
step 6 : 64
step 7 : 158
step 8 : 360
step 9 : 832
step 10 : 1764
step 11 : 4010
step 12 : 8458
step 13 : 18496
step 14 : 37006
step 15 : 77340
step 16 : 147346
step 17 : 293588
step 18 : 531052