Problem:


格子上の経路

上から見ると図 1 のような形の格子状の広場があります。この格子の各辺に「壁」があるかないかを 0 と 1 の並びで表します。点 A に立って壁に右手をつき、壁に右手をついたまま、矢印の方向に歩き続けて再び点 A に戻ってくるまでの経路を出力するプログラムを作成してください。

図1

Input

入力は９行からなり、以下の図 2 に示すように、壁がある場合を 1、ない場合を 0 として、以下の形式で与えられます。

1 行目は一番上の横線の壁の有無を左から 0 と 1 で表した文字列

2 行目はその下の縦線の壁の有無を左から0 と1 で表した文字列

3 行目は上から2 本目の横線の壁の有無を左から0 と1 で表した文字列

...

9 行目は一番下の横線の壁の有無を左から0 と1 で表した文字列

図2 (壁あるところを太線で表しています)　　(対応する数字のならび)

ただし、図１の太線に示すように、点 A から右に 1 区画分は必ず壁があるものとします。すなわち、1 行目の 1 文字目は常に 1 です。

Output

「図の左方向に一区画分進む」を 'L'、「図の右方向に一区画分進む」を 'R'、「図の上方向に一区画分進む」を 'U'、「図の下方向に一区画分進む」を 'D' で表わし、進む順に 'L', 'R', 'U', 'D' を１行に並べて出力します。

Sample Input

1111
00001
0110
01011
0010
01111
0010
01001
0111

Output for the Sample Input

RRRRDDDDLLLUUURRDDLURULLDDDRRRUUUULLLL



Sample input:
1111
00001
0110
01011
0010
01111
0010
01001
0111


Sample output:
RRRRDDDDLLLUUURRDDLURULLDDDRRRUUUULLLL

Submission status: Accepted

Solution code:
#coding: utf-8
def xxx(position, direction):
    if direction == 'R' or direction == 'L':
        if not (0 <= position[tate] <= 8 and 0 <= position[yoko] <= 3):
            return 
    elif direction == 'U' or direction == 'D':
        if not (1 <= position[tate] <= 7 and 0 <= position[yoko] <= 4):
            return
    if mapp[position[tate]][position[yoko]] == 0:
        return
    if (position[tate] == 0 and position[yoko] == 0) and direction == 'L' or \
       (position[tate] == 1 and position[yoko] == 0) and direction == 'U':
        result.append(direction)
        print ''.join(result)
        return True
    elif mapp[position[tate]][position[yoko]] == 1:
        result.append(direction)
        if kyoto(position, direction): return True

def kyoto(position, direction):
    if direction == 'R':
        #????????????????´¢
        check_position = position[tate]-1, position[yoko]+1
        direction = 'U'
        if xxx(check_position, direction): return True
        #????????????????´¢
        check_position = position[tate], position[yoko]+1
        direction = 'R'
        if xxx(check_position, direction): return True
        #????????????????´¢
        check_position = position[tate]+1, position[yoko]+1
        direction = 'D'
        if xxx(check_position, direction): return True
        #????????????????´¢
        check_position = position[tate], position[yoko]
        direction = 'L'
        if xxx(check_position, direction): return True
    elif direction == 'U':
        #????????????????´¢
        check_position = position[tate]-1, position[yoko]-1
        direction = 'L'
        if xxx(check_position, direction): return True
        #????????????????´¢
        check_position = position[tate]-2, position[yoko]
        direction = 'U'
        if xxx(check_position, direction): return True
        #????????????????´¢
        check_position = position[tate]-1, position[yoko]
        direction = 'R'
        if xxx(check_position, direction): return True
        #????????????????´¢
        check_position = position[tate], position[yoko]
        direction = 'D'
        if xxx(check_position, direction): return True
    elif direction == 'L':
        #????????????????´¢
        check_position = position[tate]+1, position[yoko]
        direction = 'D'
        if xxx(check_position, direction): return True
        #????????????????´¢
        check_position = position[tate], position[yoko]-1
        direction = 'L'
        if xxx(check_position, direction): return True
        #????????????????´¢
        check_position = position[tate]-1, position[yoko]
        direction = 'U'
        if xxx(check_position, direction): return True
        #????????????????´¢
        check_position = position[tate], position[yoko]
        direction = 'R'
        if xxx(check_position, direction): return True
    elif direction == 'D':
        #????????????????´¢
        check_position = position[tate]+1, position[yoko]
        direction = 'R'
        if xxx(check_position, direction): return True
        #????????????????´¢
        check_position = position[tate]+2, position[yoko]
        direction = 'D'
        if xxx(check_position, direction): return True
        #????????????????´¢
        check_position = position[tate]+1, position[yoko]-1
        direction = 'L'
        if xxx(check_position, direction): return True
        #????????????????´¢
        check_position = position[tate], position[yoko]
        direction = 'U'
        if xxx(check_position, direction): return True

if __name__ == '__main__':
    mapp = []
    for i in range(9):
        mapp.append([int(char) for char in raw_input()])
    tate = 0
    yoko = 1
    result = []
    xxx((0,0), 'R')

Submission status: Accepted

Solution code:
import sys

loc = [3, 1]

def print_dir(h):
    if h == 0:
        print('R', end='')
    elif h == 1:
        print('D', end='')
    elif h == 2:
        print('L', end='')
    elif h == 3:
        print('U', end='')

dir = [[1, 0], [0, 1], [-1, 0], [0, -1]]
hand = 3

board = [[0 for _ in range(11)] for _ in range(11)]
for i, line in enumerate(sys.stdin):
    for j, c in enumerate(line.strip()):
        board[i+1][1 + (i+1)%2 + j*2] = int(c)

print("R", end='')

while loc != [1, 1]:
    for i in range(4):
        if board[loc[1]+dir[(hand+i)%4][1]][loc[0]+dir[(hand+i)%4][0]] == 1:
            loc[0] += dir[(hand+i)%4][0]*2
            loc[1] += dir[(hand+i)%4][1]*2
            if i == 1:
                print_dir((hand+1)%4)
            elif i == 2:
                print_dir((hand+2)%4)
                hand = (hand+1)%4
            elif i == 3:
                print_dir((hand+3)%4)
                hand = (hand+2)%4
            elif i == 0:
                print_dir(hand%4)
                hand = (hand+3)%4

            break

print()

Submission status: Accepted

Solution code:
def wall(grid,x,y,d):
    if d==0:
        return x<4 and grid[y*2][x]=='1'
    if d==1:
        return y<4 and grid[y*2+1][x]=='1'
    if d==2:
        return x>0 and grid[y*2][x-1]=='1'
    if d==3:
        return y>0 and grid[y*2-1][x]=='1'

def move(x,y,d):
    if d==0:
        return x+1,y,'R'
    if d==1:
        return x,y+1,'D'
    if d==2:
        return x-1,y,'L'
    if d==3:
        return x,y-1,'U'

ans=''
x=y=d=0
grid=[raw_input() for i in range(9)]
while x or y or d < 2:
    d=(d+3)%4
    while not wall(grid,x,y,d):
        d=(d+1)%4
    x,y,c=move(x,y,d)
    ans=ans+c
print ans

Submission status: Accepted

Solution code:
import sys
grid=[line.strip() for line in sys.stdin.readlines()]
xgrid=["0"+grid[i]+"0" for i in xrange(9) if i%2==0]
ygrid=[grid[i] for i in xrange(9) if i%2==1]
ygrid.insert(5,"0"*5)
ygrid.insert(0,"0"*5)
graph=[[None]*5 for i in xrange(5)]
for y in xrange(5):
    for x in xrange(5):
        graph[y][x]=[ygrid[y][x],xgrid[y][x+1],ygrid[y+1][x],xgrid[y][x]]
nx,ny,dir=0,0,1
di=["U","R","D","L",]
dx=[0,1,0,-1]
dy=[-1,0,1,0]
log=[]
while True:
    for i in xrange(4):
        if graph[ny][nx][(dir+3)%4]=="1":
            dir=(dir+3)%4
            log.append(di[dir])
            nx,ny=nx+dx[dir],ny+dy[dir]
            break
        dir=(dir+1)%4
    if nx==0 and ny==0:break
print "".join(log)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

road_h = [[0 for i in range(6)] for j in range(7)] #?¨??????????
road_v = [[0 for i in range(7)] for j in range(6)] #????????????
ax = ay = 1
ad_list = ['L', 'R', 'U', 'D']

for i in range(9):
    line = str(raw_input())
    if i % 2 == 0:
        for j in range(4):
            if line[j] == '1':
                road_h[1+i/2][1+j] += 1
    else:
        for j in range(5):
            if line[j] == '1':
                road_v[1+i/2][1+j] += 1

ad = 1
ax += 1
ans = 'R'
while True:
    if ax == 1 and ay == 1:
        break
    if ad == 0:     #?????????
        if road_v[ay][ax]:
            ay += 1
            ad = 3
        elif road_h[ay][ax-1]:
            ax -= 1
        elif road_v[ay-1][ax]:
            ay -= 1
            ad = 2
        else:
            ax += 1
            ad = 1
    elif ad == 1:   #?????????
        if road_v[ay-1][ax]:
            ay -= 1
            ad = 2
        elif road_h[ay][ax]:
            ax += 1
        elif road_v[ay][ax]:
            ay += 1
            ad = 3
        else:
            ax -= 1
            ad = 0
    elif ad == 2:   #?????????
        if road_h[ay][ax-1]:
            ax -= 1
            ad = 0
        elif road_v[ay-1][ax]:
            ay -= 1
        elif road_h[ay][ax]:
            ax += 1
            ad = 1
        else:
            ay += 1
            ad = 3
    elif ad == 3:   #?????????
        if road_h[ay][ax]:
            ax += 1
            ad = 1
        elif road_v[ay][ax]:
            ay += 1
        elif road_h[ay][ax-1]:
            ax -= 1
            ad = 0
        else:
            ay -= 1
            ad = 2
    ans = ans + ad_list[ad]
print ans

Submission status: Accepted

Solution code:
import sys
n = [input() for i in range(9)]
path = [[0 for i in range(5)] for j in range(5)]

for i, v in enumerate([a[1] for a in enumerate(n) if a[0] % 2 == 0]):
    for j in range(4):
        if v[j] == '1':
            path[i][j] += 1
            path[i][j+1] += 2


for i, v in enumerate([a[1] for a in enumerate(n) if a[0] % 2 != 0]):
    for j in range(5):
        if v[j] == '1':
            path[i][j] += 4
            path[i+1][j] += 8

dur = {'R':(1, 0, 1),
       'L':(2, 0, -1),
       'U':(8, -1, 0),
       'D':(4, 1, 0)}

dur_next = {'R':('U','R','D','L'),
            'L':('D','L','U','R'),
            'U':('L','U','R','D'),
            'D':('R','D','L','U')}
def walk():
    global cx, cy
    cx = dur[d][2] + cx
    cy = dur[d][1] + cy

def next_D():
    global cx,cy,d,dur
    for nd in dur_next[d]:
        if path[cy][cx] & dur[nd][0]:
            d = nd
            break

cx = cy = 0
d = 'R'
log = []

while 1:
    log.append(d)
    walk()
    if cx == cy == 0:
        break

    next_D()

print(''.join(log))

Submission status: Accepted

Solution code:
def idx_to_wxy(x, y, idx):
    return (2 * x + 1 + (idx % 2) * (2 - idx), 2 * y + 1 + (1 - idx % 2) * (1 - idx))
ws = [[0]*11 for _ in range(11)]
for i in range(1, 10):
    if i % 2:
        ws[i][2], ws[i][4], ws[i][6], ws[i][8] = map(int, list(input()))
    else:
        ws[i][1], ws[i][3], ws[i][5], ws[i][7], ws[i][9] = map(int, list(input()))
x = y = 0
ds = list('RDLU')
d = 'R'
while True:
    print(d, end='')
    idx = ds.index(d)
    x += (idx % 2) * (2 - idx)
    y += (1 - idx % 2) * (1 - idx)
    if x == y == 0:
        break
    for i in range(-1, 3):
        if ws[idx_to_wxy(x, y, (idx + i) % 4)[0]][idx_to_wxy(x, y, (idx + i) % 4)[1]]:
            d = ds[(idx + i) % 4]
            break
print('')

Submission status: Accepted

Solution code:
import sys

point = [[[0 for i in range(4)] for j in range(5)] for k in range(5)]
raw = 0
for line in sys.stdin:
    way = list(map(int, line.strip()))
    if len(way) == 4:
        for col in range(4):
            if way[col] == 1:
                point[raw][col][1] = point[raw][col + 1][3] = 1

    elif len(way) == 5:
        for col in range(5):
            if way[col] == 1:
                point[raw][col][2] = point[raw + 1][col][0] = 1
        raw += 1

dict = {0:"U", 1:"R", 2:"D", 3:"L"}
cold = [0, 1, 0, -1]
rawd = [-1, 0, 1, 0]

raw = 0
col = 0
nowd = 1
ans = ""

while True:
    for dirc in [(x - 1) % 4 for x in range(nowd, nowd + 4)]:
        if point[raw][col][dirc] == 1:
            ans += dict[dirc]
            raw += rawd[dirc]
            col += cold[dirc]
            nowd = dirc
            break
    if raw == 0 and col == 0:
        break
        
print(ans)

Submission status: Accepted

Solution code:
def is_wall(x1,y1,x2,y2):
    if x1<0 or 4<x1 or y1<0 or 4<y1 or x2<0 or 4<x2 or y2<0 or 4<y2:
        return False
    elif x1 == x2:
        if y1>y2: y1,y2 = y2,y1
        if y2-y1 != 1: return False
        return (walls[y1*2+1][x1] == "1")
    elif y1 == y2:
        if x1>x2: x1,x2 = x2,x1
        if x2-x1 != 1: return False
        return (walls[y1*2][x1] == "1")
    else: return False

def nextmove(x,y):
    lastmove = moves[-1]
    if lastmove == 3: lastmove = -1
    if lastmove < -1: lastmove += 4
    if is_wall(x,y,x+direction[lastmove+1][1],y+direction[lastmove+1][2]):
        return lastmove+1,x+direction[lastmove+1][1],y+direction[lastmove+1][2]

    if is_wall(x,y,x+direction[lastmove][1],y+direction[lastmove][2]):
        return lastmove,x+direction[lastmove][1],y+direction[lastmove][2]

    if is_wall(x,y,x+direction[lastmove-1][1],y+direction[lastmove-1][2]):
        return lastmove-1,x+direction[lastmove-1][1],y+direction[lastmove-1][2]

    if is_wall(x,y,x+direction[lastmove-2][1],y+direction[lastmove-2][2]):
        return lastmove-2,x+direction[lastmove-2][1],y+direction[lastmove-2][2]

direction = [["R",1,0],["U",0,-1],["L",-1,0],["D",0,1]]
walls = []
moves = [0]
for _ in range(9):
    walls.append(input())
lastx = 1
lasty = 0
print("R", end = "")
while True:
    move,lastx,lasty = nextmove(lastx, lasty)
    moves.append(move)
    print(direction[move][0], end = "")
    if lastx == 0 and lasty == 0: break
print()

Submission status: Accepted

Solution code:
# Aizu Problem 0037: Path on a Grid
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")

DIRS = ['R', 'D', 'L', 'U']
DX = [0, 1, 0, -1]
DY = [1, 0, -1, 0]

board = [[[False for _ in range(4)] for __ in range(6)] for ___ in range(6)]
for i in range(9):
    l = 4 + i % 2
    walls = input().strip()
    for j in range(4 + i % 2):
        n = int(walls[j])
        if n == 1:
            if i % 2 == 0:
                board[i//2][j+1][1] = True
                board[i//2+1][j+1][3] = True
            else:
                board[i//2+1][j][0] = True
                board[i//2+1][j+1][2] = True
    
out = ""
direc = 0
nx, ny = 0, 1
while True:
    if (nx == 1 and ny == 0 and direc == 2) or \
       (nx == 0 and ny == 0 and direc == 2):
        break
    x = nx + DX[direc]
    y = ny + DY[direc]
    if not board[nx][ny][(direc+1)%4]:
        direc = (direc + 1) % 4
        nx += DX[direc]
        ny += DY[direc]
    elif board[nx][ny][direc]:
        out += DIRS[direc]
        direc = (direc - 1 + 4) % 4
    else:
        out += DIRS[direc]
        nx = x
        ny = y
print(out)

Submission status: Accepted

Solution code:
def move(position):
    x = position[0]
    y = position[1]
    d = position[2]
    if d == "L":
        p = "DLUR"
    elif d == "R":
        p = "URDL"
    elif d == "U":
        p = "LURD"
    else:
        p = "RDLU"
    for i in range(4):
        if p[i] in grid[y][x]:
            d = p[i]
            if d == "L":
                print("L",end="")
                x -= 1
                break
            elif d == "R":
                print("R",end="")
                x += 1
                break
            elif d == "U":
                print("U",end="")
                y -= 1
                break
            else:
                print("D",end="")
                y += 1
                break
    return [x, y, d]

pos = [1,1,"R"]
grid = [["" for i in range(6)] for j in range(6)]
for i in range(9):
    inp = input()
    if i%2 == 0:
        for j in range(4):
            if inp[j] == "1":
                grid[i//2 + 1][j + 1] += "R"
                grid[i//2 + 1][j + 2] += "L"
    else:
        for j in range(5):
            if inp[j] == "1":
                grid[i//2 + 1][j + 1] += "D"
                grid[i//2 + 2][j + 1] += "U"
while True:
    pos = move(pos)
    if pos[0] == 1 and pos[1] == 1:
        break
print("")

Submission status: Accepted

Solution code:
g=[[0]*5 for _ in[0]*5]
for i in range(9):
 e=input()
 for j in range(4+i%2):
  if int(e[j]):
   if i%2:g[i//2][j]+=4;g[i//2+1][j]+=1
   else:r=g[i//2];r[j]+=2;r[j+1]+=8
y,x,k=0,1,1
a='1'
while 1:
 k=k%4+2
 for _ in[0]*4:
  k+=1
  if g[y][x]&int(2**(k%4)):a+=str(k%4);break
 if k%2:x+=[1,-1][(k%4)>1]
 else:y+=[-1,1][(k%4)>0]
 if x+y==0:break
print(''.join('URDL'[int(c)]for c in a))

Submission status: Accepted

Solution code:
g=[[0]*5 for _ in[0]*5]
for i in range(9):
 e=input()
 for j in range(4+i%2):
  if int(e[j]):
   if i%2:g[i//2][j]+=4;g[i//2+1][j]+=1
   else:r=g[i//2];r[j]+=2;r[j+1]+=8
y,x=0,1
k=1
a='1'
while 1:
 k=k%4+2
 for _ in[0]*4:
  k+=1
  if g[y][x]&int(2**(k%4)):a+=str(k%4);break
 if k%2:x+=[1,-1][(k%4)>1]
 else:y+=[-1,1][(k%4)>0]
 if x+y==0:break
print(''.join('URDL'[int(c)]for c in a))

Submission status: Accepted

Solution code:
g=[[0]*5 for _ in[0]*5]
for i in range(9):
 e=input()
 for j in range(4+i%2):
  if int(e[j]):
   if i%2:g[i//2][j]+=4;g[i//2+1][j]+=1
   else:r=g[i//2];r[j]+=2;r[j+1]+=8
y,x=0,1
k=1
a='1'
while 1:
 k+=2
 for _ in[0]*4:
  k+=1
  if g[y][x]&int(2**(k%4)):a+=str(k%4);break
 if k%2:x+=[1,-1][(k%4)>1]
 else:y+=[-1,1][(k%4)>0]
 if x+y==0:break
print(''.join('URDL'[int(c)]for c in a))

Submission status: Accepted

Solution code:
class Board:
    def __init__(self,m):
        self.m = m
        self.x = 0
        self.y = 0
        self.d = 'e'

    def dir(self):
        return self.d

    def is_origin(self):
        return (self.x==0) and (self.y==0)
        
    def north_is_wall(self):
        if self.y == 0:
            return False
        else:
            if self.m[2*self.y-1][self.x] == '1':
                return True
            else:
                return False

    def east_is_wall(self):
        if self.x == 4:
            return False
        elif m[2*self.y][self.x] == '1':
            return True
        else:
            return False
    def west_is_wall(self):
        if self.x == 0:
            return False
        elif m[2*self.y][self.x-1] == '1':
            return True
        else:
            return False
    def south_is_wall(self):
#        print("x={},y={}".format(self.x,self.y))
        if self.y == 4:
            return False
        elif self.m[2*self.y+1][self.x] == '1':
            return True
        else:
            return False

    def go_north(self):
        if self.y == 0:
            raise "invalid"
        else:
            self.y -= 1
            self.d = 'n'
        print("U",end="")

    def go_south(self):
        if self.y == 5:
            raise "invalid"
        else:
            self.y += 1
            self.d = 's'
        print("D",end="")

    def go_east(self):
        if self.x == 4:
            raise "go_east"
        else:
            self.x += 1
            self.d = 'e'
        print("R",end="")

    def go_west(self):
        if self.x == 0:
            raise "go_west"
        else:
            self.x -= 1
            self.d = 'w'
        print("L",end="")


def run(m):
    b = Board(m)
    init = True
    while True:
        d = b.dir()
        if d == 'e':
            if   b.north_is_wall():
                b.go_north()
            elif b.east_is_wall():
                b.go_east()
            elif b.south_is_wall():
                b.go_south()
            else:
                b.go_west()
        elif d == 's':
            if   b.east_is_wall():
                b.go_east()
            elif b.south_is_wall():
                b.go_south()
            elif b.west_is_wall():
                b.go_west()
            else:
                b.go_north()
        elif d == 'w':
            if b.south_is_wall():
                b.go_south()
            elif b.west_is_wall():
                b.go_west()
            elif b.north_is_wall():
                b.go_north()
            else:
                b.go_east()
        elif d == 'n':
            if  b.west_is_wall():
                b.go_west()
            elif b.north_is_wall():
                b.go_north()
            elif b.east_is_wall():
                b.go_east()
            else:
                b.go_south()

        if (not init) and b.is_origin():
            print()
            break
        init = False

m = []
for _ in range(9):
    m.append(list(input()))

run(m)

Submission status: Accepted

Solution code:
g=[[0]*5 for _ in[0]*5]
for i in range(9):
 e=input()
 for j in range(4+i%2):
  if int(e[j]):
   if i%2:g[i//2][j]+=4;g[i//2+1][j]+=1
   else:r=g[i//2];r[j]+=2;r[j+1]+=8
y,x=0,1
k=1
a=[1]
while 1:
 k+=2
 for _ in[0]*4:
  k+=1
  if g[y][x]&int(2**(k%4)):a+=[k%4];break
 if k%2:x+=[1,-1][(k%4)>1]
 else:y+=[-1,1][(k%4)>0]
 if x+y==0:break
print(''.join('URDL'[c]for c in a))

Submission status: Accepted

Solution code:
g=[[0]*5 for _ in[0]*5]
for i in range(9):
 e=input()
 for j in range(4+i%2):
  if int(e[j]):
   if i%2:g[i//2][j]+=4;g[i//2+1][j]+=1
   else:r=g[i//2];r[j]+=2;r[j+1]+=8
y,x=0,1
k=1
a=[1]
while 1:
 k+=2
 for _ in[0]*4:
  k+=1
  if g[y][x]&int(2**(k%4)):a+=[k%4];break
 if k%2:x+=1-2*((k%4)>1)
 else:y+=2*((k%4)>0)-1
 if x+y==0:break
print(''.join('URDL'[c]for c in a))

Submission status: Accepted

Solution code:
g=[[0]*5 for _ in[0]*5]
for i in range(9):
 e=input()
 for j in range(4+i%2):
  if int(e[j]):
   if i%2:g[i//2][j]+=4;g[i//2+1][j]+=1
   else:r=g[i//2];r[j]+=2;r[j+1]+=8
y,x=0,1
k=1
a=[1]
while 1:
 k+=2
 for _ in[0]*4:
  k+=1
  if g[y][x]&int(2**(k%4)):a+=[k%4];break
 if k%2:x+=1-2*((k%4)>1)
 else:y+=2*((k%4)>0)-1
 if x+y<1:break
print(''.join('URDL'[c]for c in a))

Submission status: Accepted

Solution code:
# AOJ 0037: Path on a Grid
# Python3 2018.6.27 bal4u

next = [[1,2,4,8],[4,8,1,2],[8,1,2,4],[2,4,8,1]]
tbl = [[0 for c in range(5)] for r in range(5)]

def move(k):
	global r, c, last, ans
	if k == 1:
		r -= 1
		last = 2
		ans += 'U'
	elif k == 2:
		c += 1
		last = 0
		ans += 'R'
	elif k == 4:
		r += 1
		last = 3
		ans += 'D'
	else:
		c -= 1
		last = 1
		ans += 'L'

for i in range(9):
	a = input()
	r = i >> 1
	if i & 1:
		for c in range(5):
			if a[c] == '1':
				tbl[r  ][c] |= 4
				tbl[r+1][c] |= 1
	else:
		for c in range(4):
			if a[c] == '1':
				tbl[r][c  ] |= 2
				tbl[r][c+1] |= 8

ans = ""
r, c, last = 0, 0, 0
while True:
	for i in range(4):
		if tbl[r][c] & next[last][i]:
			move(next[last][i])
			break;
	if r == 0 and c == 0: break
print(ans)

Submission status: Accepted

Solution code:
class Coordinate(object):
    def __init__(self):
        self.path = [None, None, None, None]


class Maze(object):
    def __init__(self):
        self.a = [[Coordinate() for _ in [0]*5] for _ in [0]*5]

    def get_room(self, x, y):
        return self.a[y][x]

    def set_path(self, pos1, pos2):
        dir1, dir2 = (0, 2) if pos1[1] == pos2[1] else (1, 3)
        self.get_room(*pos1).path[dir1] = pos2
        self.get_room(*pos2).path[dir2] = pos1

    def solve(self):
        result, x, y, direction = "R", 1, 0, 0
        direction_sign = "RDLU"

        while not(x == 0 and y == 0):
            current = self.get_room(x, y)
            if current.path[(direction-1)%4]:
                direction = (direction-1)%4
            elif current.path[direction]:
                pass
            elif current.path[(direction+1)%4]:
                direction = (direction+1)%4
            else:
                direction = (direction+2)%4
            x, y = current.path[direction]
            result += direction_sign[direction]

        return result


maze = Maze()
for i in range(9):
    y = i//2
    dx, dy = (1, 0) if i%2 == 0 else (0, 1)
    for x, c in enumerate(input()):
        if c == "1":
            maze.set_path((x, y), (x+dx, y+dy))

print(maze.solve())

Submission status: Accepted

Solution code:
import sys
grid=[line.strip() for line in sys.stdin.readlines()]
xgrid=["0"+grid[i]+"0" for i in xrange(9) if i%2==0]
ygrid=[grid[i] for i in xrange(9) if i%2==1]
ygrid.insert(5,"0"*5)
ygrid.insert(0,"0"*5)
graph=[[None]*5 for i in xrange(5)]
for y in xrange(5):
    for x in xrange(5):
        graph[y][x]=[ygrid[y][x],xgrid[y][x+1],ygrid[y+1][x],xgrid[y][x]]
nx,ny,dir=0,0,1
DIRECTION=["U","R","D","L",]
dx=[0,1,0,-1]
dy=[-1,0,1,0]
log=[]
while True:
    for i in xrange(4):
        if graph[ny][nx][(dir+3)%4]=="1":
            dir=(dir+3)%4
            log.append(DIRECTION[dir])
            nx,ny=nx+dx[dir],ny+dy[dir]
            break
        dir=(dir+1)%4
    if nx==0 and ny==0:break
print "".join(log)

Submission status: Accepted

Solution code:
import sys

def read_inputs():
    inputs = []
    for i in range(9):
        try:
            inputs.append(raw_input())
        except EOFError:
            sys.exit()
    return inputs

def create_routes(inputs):
    for y, line in enumerate(inputs):
        for x, c in enumerate(list(line)):
            if c == '1':
                if y % 2 == 0:
                    dots[y/2][x]["R"] = 1
                    dots[y/2][x+1]["L"] = 1
                else:
                    dots[y/2][x]["D"] = 1
                    dots[y/2+1][x]["U"] = 1

def move_person(dots):
    ret, current = "", "R"
    x, y = 0, 0

    def find(indexs):
        dic = ("R", "D", "L", "U",)
        for i in indexs:
            if dots[y][x][dic[i]]:
                return dic[i]
        return ""

    while True:
        ret += current
        if current == "R":
            x += 1
            current = find([3, 0, 1, 2])
        elif current == "D":
            y += 1
            current = find([0, 1, 2, 3])
        elif current == "L":
            x -= 1
            current = find([1, 2, 3, 0])
        elif current == "U":
            y -= 1
            current = find([2, 3, 0, 1])
        else:
            print "wrong data"
        if x == 0 and y == 0:
            break
    return ret

dots = [[{'U': 0, 'D': 0, 'L': 0, 'R': 0} for i in range(5)] for j in range(5)]

inputs = read_inputs()

create_routes(inputs)

print move_person(dots)

Submission status: Accepted

Solution code:
def wall(d, x, y, z):
    if z == 0: return x < 4 and d[y * 2][x] == '1'
    if z == 1: return y < 4 and d[y * 2 + 1][x] == '1'
    if z == 2: return x > 0 and d[y * 2][x - 1] == '1'
    if z == 3: return y > 0 and d[y * 2 - 1][x] == '1'
def move(x, y, z):
    if z == 0: return (x + 1, y, 'R')
    if z == 1: return (x, y + 1, 'D')
    if z == 2: return (x - 1, y, 'L')
    if z == 3: return (x, y - 1, 'U')
d = []
p = ""
x = y = z = 0
for i in range(9):
    d.append(raw_input())
while x != 0 or y != 0 or z < 2:
    z = (z + 3) % 4
    while not wall(d, x, y, z):
        z = (z + 1) % 4
    (x, y, c) = move(x, y, z)
    p += c
print p

Submission status: Accepted

Solution code:

import sys


class Grid:
    def __init__(self, lines):
        lines = map((lambda line: list(line)), lines)
        l = []
        for i in range(len(lines)):
            if i % 2 == 0:
                l.append(intersperse2(lines[i], '+'))
            else:
                l.append(intersperse(lines[i], 'x'))
        l.insert(0, ['0','x','0','x','0','x','0','x','0'])
        l.append(['0','x','0','x','0','x','0','x','0'])
        l = map(lambda x: self._outer(x), l)
        self.grid = l

    def show(self):
        for l in self.grid:
            print l
        return self

    def _outer(self, lis):
        if lis[0] == '0' or lis[0] == '1':
            lis.insert(0, 'x')
        else:
            lis.insert(0, '0')
        if lis[-1] == '0' or lis[-1] == '1':
            lis.append('x')
        else:
            lis.append('0')
        return lis


class Walker:
    def __init__(self, grid, x, y):
        self.grid = grid
        self.x = x
        self.y = y
        self.dir = 'R'

    def walk(self):
        if self.left() == '1':
            return self.to_left()
        elif self.ahead() == '1':
            return self.to_ahead()
        elif self.right() == '1':
            return self.to_right()
        else:
            return self.to_back()

    def left(self):
        x = self.x
        y = self.y
        d = self.dir
        if d == 'R':
            return self.grid.grid[y-1][x]
        elif d == 'L':
            return self.grid.grid[y+1][x]
        elif d == 'U':
            return self.grid.grid[y][x-1]
        else:   # d == 'D'
            return self.grid.grid[y][x+1]

    def ahead(self):
        x = self.x
        y = self.y
        d = self.dir
        if d == 'R':
            return self.grid.grid[y][x+1]
        elif d == 'L':
            return self.grid.grid[y][x-1]
        elif d == 'U':
            return self.grid.grid[y-1][x]
        else:   # d == 'D'
            return self.grid.grid[y+1][x]

    def right(self):
        x = self.x
        y = self.y
        d = self.dir
        if d == 'R':
            return self.grid.grid[y+1][x]
        elif d == 'L':
            return self.grid.grid[y-1][x]
        elif d == 'U':
            return self.grid.grid[y][x+1]
        else:   # d == 'D'
            return self.grid.grid[y][x-1]

    def to_left(self):
        d = self.dir
        if d == 'R':
            self.y -= 2
            self.dir = 'U'
            return 'U'
        elif d == 'L':
            self.y += 2
            self.dir = 'D'
            return 'D'
        elif d == 'U':
            self.x -= 2
            self.dir = 'L'
            return 'L'
        else:   # d == 'D'
            self.x += 2
            self.dir = 'R'
            return 'R'

    def to_ahead(self):
        d = self.dir
        if d == 'R':
            self.x += 2
            return 'R'
        elif d == 'L':
            self.x -= 2
            return 'L'
        elif d == 'U':
            self.y -= 2
            return 'U'
        else:   # d == 'D'
            self.y += 2
            return 'D'

    def to_right(self):
        d = self.dir
        if d == 'R':
            self.y += 2
            self.dir = 'D'
            return 'D'
        elif d == 'L':
            self.y -= 2
            self.dir = 'U'
            return 'U'
        elif d == 'U':
            self.x += 2
            self.dir = 'R'
            return 'R'
        else:   # d == 'D'
            self.x -= 2
            self.dir = 'L'
            return 'L'

    def to_back(self):
        d = self.dir
        if d == 'R':
            self.x -= 2
            self.dir = 'L'
            return 'L'
        elif d == 'L':
            self.x += 2
            self.dir = 'R'
            return 'R'
        elif d == 'U':
            self.y += 2
            self.dir = 'D'
            return 'D'
        else:   # d == 'D'
            self.y -= 2
            self.dir = 'U'
            return 'U'



def intersperse(lis, s):
    r = []
    for a in lis:
        r.append(a)
        r.append(s)
    r.pop()
    return r

def intersperse2(lis, s):
    r = []
    for a in lis:
        r.append(s)
        r.append(a)
    r.append(s)
    return r



lines = sys.stdin.readlines()
lines = map(lambda x: x.rstrip("\r\n"), lines)
grid = Grid(lines)
walker = Walker(grid, 1, 1)
path = []
while True:
    path.append(walker.walk())
    if (walker.x, walker.y) == (1,1):
        break
print ''.join(path)

Submission status: Accepted

Solution code:
def wall(grid,x,y,d):
    if d==0: return x<4 and grid[y*2][x]=='1'
    if d==1: return y<4 and grid[y*2+1][x]=='1'
    if d==2: return x>0 and grid[y*2][x-1]=='1'
    if d==3: return y>0 and grid[y*2-1][x]=='1'

def move(x,y,d):
    if d==0: return (x+1,y,'R')
    if d==1: return (x,y+1,'D')
    if d==2: return (x-1,y,'L')
    if d==3: return (x,y-1,'U')

path=""
x=y=d=0
grid=[raw_input() for i in range(9)]
while x!=0 or y!=0 or d<2:
    d=(d+3)%4
    while not wall(grid,x,y,d):
        d=(d+1)%4
    (x,y,c)=move(x,y,d)
    path+=c
print path