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: Wrong Answer

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':('D','L','U'),
            'U':('L','U','R'),
            'D':('R','D','L')}
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: Wrong Answer

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"
print(*grid,sep="\n")
while True:
    pos = move(pos)
    if pos[0] == 1 and pos[1] == 1:
        break

Submission status: Wrong Answer

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+3
 for i in range(4):
  k=k+i
  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: Wrong Answer

Solution code:
grid = []
for i in range(9):
    grid += [input()]

position = [0, 0]
direction = 'R'
path = ''
while True:
    if direction == 'R':
        path += direction
        position[1] += 1
        if position[1] == 4 or grid[position[0]][position[1]] == '0':
            if position[0] > 0 and grid[position[0] - 1][position[1]] == '1':
                direction = 'U'
            elif position[0] < 8 and grid[position[0] + 1][position[1]] == '1':
                direction = 'D'
            else:
                direction = 'L'
    elif direction == 'L':
        path += direction
        position[1] -= 1
        if position[1] == 0 or grid[position[0]][position[1] - 1] == '0':
            if position[0] < 8 and grid[position[0] + 1][position[1]] == '1':
                direction = 'D'
            elif position[0] > 0 and grid[position[0] - 1][position[1]] == '1':
                direction = 'U'
            else:
                if position[0] == position[1] == 0:
                    break
                direction = 'R'
    elif direction == 'D':
        path += direction
        position[0] += 2
        if position[0] == 8 or grid[position[0] + 1][position[1]] == '0':
            if position[1] < 4 and grid[position[0]][position[1]] == '1':
                direction = 'R'
            elif position[1] > 0 and grid[position[0]][position[1] - 1] == '1':
                direction = 'L'
            else:
                direction = 'U'
    else:
        path += direction
        position[0] -= 2
        if position[0] == 0 or grid[position[0] - 1][position[1]] == '0':
            if position[1] > 0 and grid[position[0]][position[1] - 1] == '1':
                direction = 'L'
            elif position[1] < 4 and grid[position[0]][position[1]] == '1':
                direction = 'R'
            else:
                direction = 'D'
print(path)

Submission status: Wrong Answer

Solution code:
grid = []
for i in range(9):
    grid += [input()]

position = [0, 0]
direction = 'R'
path = ''
while True:
    print(direction)
    if direction == 'R':
        path += direction
        position[1] += 1
        if position[0] > 0 and grid[position[0] - 1][position[1]] == '1':
            direction = 'U'
        elif position[1] < 4 and grid[position[0]][position[1]] == '1':
            direction = 'R'
        elif position[0] < 8 and grid[position[0] + 1][position[1]] == '1':
            direction = 'D'
        else:
            direction = 'L'
    elif direction == 'L':
        path += direction
        position[1] -= 1
        if position[0] < 8 and grid[position[0] + 1][position[1]] == '1':
            direction = 'D'
        elif position[1] > 0 and grid[position[0]][position[1] - 1] == '1':
            direction = 'L'
        elif position[0] > 0 and grid[position[0] - 1][position[1]] == '1':
            direction = 'U'
        else:
            if position[0] == position[1] == 0:
                break
            direction = 'R'
    elif direction == 'D':
        path += direction
        position[0] += 2
        if position[1] < 4 and grid[position[0]][position[1]] == '1':
            direction = 'R'
        elif position[0] < 8 and grid[position[0] + 1][position[1]] == '1':
            direction = 'D'
        elif position[1] > 0 and grid[position[0]][position[1] - 1] == '1':
            direction = 'L'
        else:
            direction = 'U'
    else:
        path += direction
        position[0] -= 2
        if position[1] > 0 and grid[position[0]][position[1] - 1] == '1':
            print('hello')
            direction = 'L'
        elif position[0] > 0 and grid[position[0] - 1][position[1]] == '1':
            direction = 'U'
        elif position[1] < 4 and grid[position[0]][position[1]] == '1':
            direction = 'R'
        else:
            direction = 'D'
print(path)

Submission status: Wrong Answer

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**((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: Wrong Answer

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)>0)
 else:y+=2*((k%4)>0)-1
 if x+y==0:break
print(''.join('URDL'[c]for c in a))

Submission status: Wrong Answer

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)]
#0->north 1->east...
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]]

#right hand ->dir+1
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+1)%4]=="1":
            dir=(dir+1)%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: Wrong Answer

Solution code:
dist = ['D','L','U','R']
dict = [(0,1),(1,0),(0,-1),(-1,0)]

result = ''
sell = [[False]*13]*2
for i in xrange(9):
    l = [False,False]
    s = raw_input()
    if len(s) == 4:
        for j in s:
            l.append(False)
            l.append(bool(int(j)))
        l += [False] * 3
    else:
        for j in s:
            l.append(bool(int(j)))
            l.append(False)
        l += [False] * 2
    sell.append(l)
sell += [[False]*13]*2

my = (2,2,0)

while(True):
    if sell[my[0]+dict[my[2]][0]][my[1]+dict[my[2]][1]]:
        my = (my[0]+dict[my[2]][0]*2,my[1]+dict[my[2]][1]*2,my[2])
        if my[0] == 2 and my[1] == 2:
            break
        else:
            my = (my[0],my[1],(my[2]-1)%4)
            result += dist[my[2]]
    else:
        my = (my[0],my[1],(my[2]+1)%4)

print result

Submission status: Wrong Answer

Solution code:
dist = ['D','L','U','R']
dict = [(0,1),(1,0),(0,-1),(-1,0)]

result = ''
sell = [[False]*13]*2
for i in xrange(9):
    l = [False,False]
    s = raw_input()
    if len(s) == 4:
        for j in s:
            l.append(False)
            l.append(bool(int(j)))
        l += [False] * 3
    else:
        for j in s:
            l.append(bool(int(j)))
            l.append(False)
        l += [False] * 2
    sell.append(l)
sell += [[False]*13]*2

my = (2,2,0)

while(True):
    if sell[my[0]+dict[my[2]][0]][my[1]+dict[my[2]][1]]:
        my = (my[0]+dict[my[2]][0]*2,my[1]+dict[my[2]][1]*2,my[2])
        result += dist[my[2]]
        if my[0] == 2 and my[1] == 2:
            break
        else:
            my = (my[0],my[1],(my[2]-1)%4)
    else:
        my = (my[0],my[1],(my[2]+1)%4)

print result

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
wx=[]
wy=[]

def readdata():
    it=0
    x=[]
    y=[]
    while True:
        try: tmp = map(int,raw_input())
        except:
            return x,y
        if it%2==0:
            x.append(tmp)
        else:
            y.append(tmp)
        it +=1

def nextpath(p, dir0):
# 0:north, 1:east, 2:south, 3:west
    tmp = ispath(p, (dir0+3)%4)
    if tmp!=[]: return tmp
    tmp = ispath(p, dir0)
    if tmp!=[]: return tmp
    tmp = ispath(p, (dir0+1)%4)
    if tmp!=[]: return tmp
    tmp = ispath(p, (dir0+2)%4)
    if tmp!=[]: return tmp
    return tmp

def ispath(p,dir1):
    y,x = p
    if dir1==0:
        if y>0 and wy[y-1][x]==1: return [-1,0]
        else: return []
    elif dir1==1:
        if x<len(wx[0]) and wx[y][x]==1: return [0,1]
        else: return []
    elif dir1==2:
        if y<len(wy[0])-1 and wy[y][x]==1: return [1,0]
        else: return []
    elif dir1==3:
        if x>0 and wx[y][x-1]==1: return [0,-1]
        else: return []
    return []

def f0037():
    p =[0,0]
    direction = 1
    msg = []
    while True:
        dp = nextpath(p, direction)
        p[0] += dp[0]
        p[1] += dp[1]
        if dp == [0,1]:
            direction = 1
            msg.append("R")
        elif dp == [0,-1]:
            direction = 3
            msg.append("L")
        elif dp == [1,0]:
            direction = 2
            msg.append("U")
        elif dp == [-1,0]:
            direction = 0
            msg.append("U")
        if p==[0,0]: break            
    return msg

wx, wy = readdata()
msg = f0037()    
print "".join(msg)

Submission status: Wrong Answer

Solution code:
wx=[]
wy=[]

def readdata():
    z=[]
    try:
        while True:
            z.append(raw_input())
    except: return z

def nextpath(p, dir0):
    for e in [3,0,1,2]:
        dp = ispath(p, (dir0+e)%4)
        if dp!=[]: break
    return dp

def ispath(p, dir1):
    y,x = p
    dp = []
    if   dir1==0 and y>0            and wy[y-1][x]=="1": dp= 0
    elif dir1==1 and x<len(wx[0])   and wx[y][x]  =="1": dp = 1
    elif dir1==2 and y<len(wy[0])-1 and wy[y][x]  =="1": dp = 2
    elif dir1==3 and x>0            and wx[y][x-1]=="1": dp = 3
    return dp

def f0037():
    p =[0,0]
    dp = 1
    msg = []
    while True:
        dp = nextpath(p, dp)
        p[0]+=[-1,0,1,0][dp]
        p[1]+=[0,1,0,-1][dp]
        if p==[0,0]: break            
        msg.append("URDL"[dp])
    return msg

z = readdata()
wx = z[0::2]
wy = z[1::2]
msg = f0037()    
print "".join(msg)

Submission status: Wrong Answer

Solution code:
wx=[]
wy=[]

def readdata():
    z=[]
    try:
        while True:
            z.append(raw_input())
    except: return z

def nextpath(p,dir0):
    for e in [3,0,1,2]:
        d = (dir0+e)%4
        if ispath(p,d): return d
    return None

def ispath(p,d):
    y,x = p
    f="0"
    try:
        if   d==0: f = wy[y-1][x]
        elif d==1: f = wx[y][x]
        elif d==2: f = wy[y][x]
        elif d==3: f = wx[y][x-1]
    except: pass
    return f=="1"

def f0037():
    p =[0,0]
    dp = 1
    msg = []
    while True:
        dp = nextpath(p, dp)
        p[0]+=[-1,0,1,0][dp]
        p[1]+=[0,1,0,-1][dp]
        msg.append("URDL"[dp])
        if p==[0,0]: break
    return "".join(msg)

z = readdata()
wx = z[0::2]
wy = z[1::2]
print f0037()

Submission status: Time Limit Exceeded

Solution code:
import sys
f = sys.stdin


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

step = {(-1, 0 ):'L',(0, -1 ):'U',(1, 0 ):'R',(0, 1):'D'}
    
    
start = pre_loc = 1 + 1j
loc = 3 + 1j
print('R',end='')
while loc != start:
    for direct in [(pre_loc - loc) / 2 * 1j ** (i + 1) for i in range(3)]:
        if board[int(loc.imag + direct.imag)][int(loc.real + direct.real)]:
            pre_loc = loc
            loc += direct * 2
            print(step[(direct.real,direct.imag)],end='')
            break
print()

Submission status: Time Limit Exceeded

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
    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
    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
    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
    ans = ans + ad_list[ad]
print ans

Submission status: Time Limit Exceeded

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()

    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 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)
#grid.show()
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:
k = [[1,2,4,8],[4,8,1,2],[8,1,2,4],[2,4,8,1]]
m = [[0]*5 for _ in range(5)]

for i in range(9):
    a = input()
    if i%2:
        for j in range(5):
            if a[j] == '1':
                m[i//2][j] |= 4
                m[i//2+1][j] |= 1
    else:
        for j in range(4):
            if a[j] == '1':
                m[i//2][j] |= 2
                m[i//2][j+1] |= 8
y,x,direct = 0,0,0
ans = []
while True:
    for i in range(4):
        if m[y][x] & k[direct][i]:
            d = k[direct][i]
            if   d == 1: y -= 1; direct = 2
            elif d == 2: x += 1; direct = 0
            elif d == 4: y += 1; direct = 3
            else       : x -= 1; direct = 1
            ans.append(direct)
            break
    if not ( x or y ): break
print("".join("RLUD"[e] for e in ans))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

def iswall(x,y,di):
  if di == 0: return x<4 and d[2*y][x] == "1"
  if di == 1: return y<4 and d[2*y+1][x] == "1"
  if di == 2: return x>0 and d[2*y][x-1] == "1"
  if di == 3: return y>0 and d[2*y-1][x] == "1"
def nextdi(x,y,di):
  di = (di-1) %4
  while True:
    if iswall(x,y,di): return di
    else: di = (di+1) % 4
def move(x,y,di):
  return x+[1,0,-1,0][di],y+[0,1,0,-1][di]

x,y,di,d,s=0,0,0,[],""
for i in xrange(9): d.append(raw_input())
while True:
  di = nextdi(x,y,di)
  x,y = move(x,y,di)
  s += ["R","D","L","U"][di]
  if (x,y) == (0,0): break
print s

Submission status: Accepted

Solution code:
import sys
f = sys.stdin

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

step = {(-1, 0 ):'L',(0, -1 ):'U',(1, 0 ):'R',(0, 1):'D'}
    
    
start = pre_loc = 1 + 1j
loc = 3 + 1j
print('R',end='')
while loc != start:
    for direct in [(pre_loc - loc) / 2 * 1j ** (i + 1) for i in range(4)]:
        if board[int(loc.imag + direct.imag)][int(loc.real + direct.real)]:
            pre_loc = loc
            loc += direct * 2
            print(step[(direct.real,direct.imag)],end='')
            break
print()

Submission status: Accepted

Solution code:
def go(human): #1:left,2:pro,3:right,4;back
    if human[2]==0: #human's direction is east
        if(human[1]*2-1>=0 and wall[human[1]*2-1][human[0]]=='1'):
            return 3
        elif (human[0]<=3 and wall[human[1]*2][human[0]]=='1'):
            return 0
        elif (human[1]*2+1<=8 and wall[human[1]*2+1][human[0]]=='1'):
            return 1
        else:
            return 2
    if human[2]==1: #south
        if(human[0]<=3 and wall[human[1]*2][human[0]]=='1'):
            return 3
        elif (human[1]*2+1<=8 and wall[human[1]*2+1][human[0]]=='1'):
            return 0
        elif (human[0]-1>=0 and wall[human[1]*2][human[0]-1]=='1'):
            return 1
        else:
            return 2
    if human[2]==2: #west
        if(human[1]*2+1<=8 and wall[human[1]*2+1][human[0]]=='1'):
            return 3
        elif (human[0]-1>=0 and wall[human[1]*2][human[0]-1]=='1'):
            return 0
        elif (human[1]*2-1>=0 and wall[human[1]*2-1][human[0]]=='1'):
            return 1
        else:
            return 2
    if human[2]==3: #north
        if(human[0]-1>=0 and wall[human[1]*2][human[0]-1]=='1'):
            return 3
        elif (human[1]*2-1>=0 and wall[human[1]*2-1][human[0]]=='1'):
            return 0
        elif (human[0]<=3 and wall[human[1]*2][human[0]]=='1'):
            return 1
        else:
            return 2

        # if human[2]==0:
        #     if(wall[0][human[0]]==1):
        #         return 2
        #     elif(wall[1][human[0]]==1):
        #         return 3
        #     else:
        #         return 4
        # elif human[2]==8:
        #     if (wall[7][human[0]]==1):
        #         return 2
        #     elif()
wall=[]
while True:
    try:
        for i in range(9):
            wall.append(raw_input())
    except:
        break

solve="R"
human=(1,0,0)
while human[0]!=0 or human[1]!=0:
    direction=(human[2]+go(human))%4
    if direction == 0:
        human=(human[0]+1,human[1],direction)
        solve+="R"
    elif direction == 1:
        human=(human[0],human[1]+1,direction)
        solve+="D"
    elif direction == 2:
        human=(human[0]-1,human[1],direction)
        solve+="L"
    else:
        human=(human[0],human[1]-1,direction)
        solve+="U"
print solve