# 20 21 22 23 24
# 15 16 17 18 19
# 10 11 12 13 14
# 05 06 07 08 09
# 00 01 02 03 04
# 0
# 3 1
# 2
def read_field( ) :
return sum ( [ int ( input ( ) .strip ( ) [ ::-1 ] .replace ( 'R' , '1' ) .replace ( 'W' , '0' ) , 2 ) << ( i*5 ) for i in range ( 4 , -1 , -1 ) ] )
def print_field( field) :
print ( hex ( field) )
for i in range ( 4 , -1 , -1 ) :
print ( *[ 'WR' [ field>> i*5 +j&1 ] for j in range ( 5 ) ] )
def new_state( pos, went, field) :
return pos<< 27 |went<< 25 |field
def get_pos( state) :
return state>> 27
def get_went( state) :
return state>> 25 &3
def get_field( state) :
return state&( 1 << 25 ) -1
def go_left( state) :
pos= get_pos( state)
return new_state( pos-1 , 3 , 1 << pos-1 ^get_field( state) ) if get_went( state) != 1 and pos%5 > 0 else -1
def go_right( state) :
pos= get_pos( state)
return new_state( pos+1 , 1 , 1 << pos+1 ^get_field( state) ) if get_went( state) != 3 and pos%5 < 4 else -1
def go_up( state) :
pos= get_pos( state)
return new_state( pos+5 , 0 , 1 << pos+5 ^get_field( state) ) if get_went( state) != 2 and pos//5 < 4 else -1
def go_down( state) :
pos= get_pos( state)
return new_state( pos-5 , 2 , 1 << pos-5 ^get_field( state) ) if get_went( state) != 0 and pos//5 > 0 else -1
field= read_field( )
print_field( field)
first= new_state( 0 , 0 , field^1 )
stateset= set ( )
stateset.add ( first)
steps= [ first]
for i in range ( 17 ) :
print ( 'step' , i+1 , ':' , len ( steps) )
temp= [ ]
for current in steps:
for func in [ go_left, go_right, go_up, go_down] :
step= func( current)
if step!= -1 and not step in stateset:
stateset.add ( step)
temp.append ( step)
steps= temp
print ( 'step' , 18 , ':' , len ( steps) )
CiMgMjAgMjEgMjIgMjMgMjQKIyAxNSAxNiAxNyAxOCAxOQojIDEwIDExIDEyIDEzIDE0CiMgMDUgMDYgMDcgMDggMDkKIyAwMCAwMSAwMiAwMyAwNAoKIyAgIDAKIyAzICAgMQojICAgMgoKZGVmIHJlYWRfZmllbGQoKToKICAgIHJldHVybiBzdW0oW2ludChpbnB1dCgpLnN0cmlwKClbOjotMV0ucmVwbGFjZSgnUicsJzEnKS5yZXBsYWNlKCdXJywnMCcpLDIpPDwoaSo1KWZvciBpIGluIHJhbmdlKDQsLTEsLTEpXSkKZGVmIHByaW50X2ZpZWxkKGZpZWxkKToKICAgIHByaW50KGhleChmaWVsZCkpCiAgICBmb3IgaSBpbiByYW5nZSg0LC0xLC0xKToKICAgICAgICBwcmludCgqWydXUidbZmllbGQ+PmkqNStqJjFdZm9yIGogaW4gcmFuZ2UoNSldKQoKZGVmIG5ld19zdGF0ZShwb3Msd2VudCxmaWVsZCk6CiAgICByZXR1cm4gcG9zPDwyN3x3ZW50PDwyNXxmaWVsZApkZWYgZ2V0X3BvcyhzdGF0ZSk6CiAgICByZXR1cm4gc3RhdGU+PjI3CmRlZiBnZXRfd2VudChzdGF0ZSk6CiAgICByZXR1cm4gc3RhdGU+PjI1JjMKZGVmIGdldF9maWVsZChzdGF0ZSk6CiAgICByZXR1cm4gc3RhdGUmKDE8PDI1KS0xCmRlZiBnb19sZWZ0KHN0YXRlKToKICAgIHBvcz1nZXRfcG9zKHN0YXRlKQogICAgcmV0dXJuIG5ld19zdGF0ZShwb3MtMSwzLDE8PHBvcy0xXmdldF9maWVsZChzdGF0ZSkpIGlmIGdldF93ZW50KHN0YXRlKSE9MSBhbmQgcG9zJTU+MCBlbHNlIC0xCmRlZiBnb19yaWdodChzdGF0ZSk6CiAgICBwb3M9Z2V0X3BvcyhzdGF0ZSkKICAgIHJldHVybiBuZXdfc3RhdGUocG9zKzEsMSwxPDxwb3MrMV5nZXRfZmllbGQoc3RhdGUpKSBpZiBnZXRfd2VudChzdGF0ZSkhPTMgYW5kIHBvcyU1PDQgZWxzZSAtMQpkZWYgZ29fdXAoc3RhdGUpOgogICAgcG9zPWdldF9wb3Moc3RhdGUpCiAgICByZXR1cm4gbmV3X3N0YXRlKHBvcys1LDAsMTw8cG9zKzVeZ2V0X2ZpZWxkKHN0YXRlKSkgaWYgZ2V0X3dlbnQoc3RhdGUpIT0yIGFuZCBwb3MvLzU8NCBlbHNlIC0xCmRlZiBnb19kb3duKHN0YXRlKToKICAgIHBvcz1nZXRfcG9zKHN0YXRlKQogICAgcmV0dXJuIG5ld19zdGF0ZShwb3MtNSwyLDE8PHBvcy01XmdldF9maWVsZChzdGF0ZSkpIGlmIGdldF93ZW50KHN0YXRlKSE9MCBhbmQgcG9zLy81PjAgZWxzZSAtMQoKCmZpZWxkPXJlYWRfZmllbGQoKQpwcmludF9maWVsZChmaWVsZCkKCmZpcnN0PW5ld19zdGF0ZSgwLDAsZmllbGReMSkKc3RhdGVzZXQ9c2V0KCkKc3RhdGVzZXQuYWRkKGZpcnN0KQoKc3RlcHM9W2ZpcnN0XQoKZm9yIGkgaW4gcmFuZ2UoMTcpOgogICAgcHJpbnQoJ3N0ZXAnLGkrMSwnOicsbGVuKHN0ZXBzKSkKICAgIHRlbXA9W10KICAgIGZvciBjdXJyZW50IGluIHN0ZXBzOgogICAgICAgIGZvciBmdW5jIGluIFtnb19sZWZ0LGdvX3JpZ2h0LGdvX3VwLGdvX2Rvd25dOgogICAgICAgICAgICBzdGVwPWZ1bmMoY3VycmVudCkKICAgICAgICAgICAgaWYgc3RlcCE9LTEgYW5kIG5vdCBzdGVwIGluIHN0YXRlc2V0OgogICAgICAgICAgICAgICAgc3RhdGVzZXQuYWRkKHN0ZXApCiAgICAgICAgICAgICAgICB0ZW1wLmFwcGVuZChzdGVwKQogICAgc3RlcHM9dGVtcAoKcHJpbnQoJ3N0ZXAnLDE4LCc6JyxsZW4oc3RlcHMpKQ==