timus_1008.py

timus_1008.py

#!/usr/bin/python2.7
"""
TIMUS 1008

ACCEPTED

2014-04-09
"""

# init
l = str(raw_input()).split(' ')
n = 0; fx = 0; fy = 0
pos = []
rel = []

def cal1(): # 2->1
    idx = -1
    pos.append((fx, fy))
    for i in range(0, n):
        idx += 1
        if idx > len(pos):
            break
        cx = pos[idx][0]
        cy = pos[idx][1]
        for c in rel[i]:
            if c == "R":
                pos.append((cx+1, cy))
            elif c == "T":
                pos.append((cx, cy+1))
            elif c == "L":
                pos.append((cx-1, cy))
            elif c == "B":
                pos.append((cx, cy-1))
            else:
                break

    print len(pos)
    for s in sorted(pos):
        print s[0], s[1]

def cal2():
    h = set(pos)
    h.remove(pos[0])
    p = 0
    stk = [pos[0]]
    p = -1
    print pos[0][0], pos[0][1]
    rel = []
    while p != len(stk) - 1:
        p += 1
        rel.append("")
        #print p, h, stk
        if (stk[p][0] + 1, stk[p][1]) in h:
            rel[p] = rel[p] + "R"
            h.remove((stk[p][0] + 1, stk[p][1]))
            stk.append((stk[p][0] + 1, stk[p][1]))

        if (stk[p][0], stk[p][1] + 1) in h:
            rel[p] = rel[p] + "T"
            h.remove((stk[p][0], stk[p][1] + 1))
            stk.append((stk[p][0], stk[p][1] + 1))

        if (stk[p][0] - 1, stk[p][1]) in h:
            rel[p] = rel[p] + "L"
            h.remove((stk[p][0] - 1, stk[p][1]))
            stk.append((stk[p][0] - 1, stk[p][1]))

        if (stk[p][0], stk[p][1] - 1) in h:
            rel[p] = rel[p] + "B"
            h.remove((stk[p][0], stk[p][1] - 1))
            stk.append((stk[p][0], stk[p][1] - 1))

        if p != n - 1:
            rel[p] += ","
        else:
            rel[p] += "."
    print "\n".join(rel)

if len(l) == 2:
    fx = int(l[0])
    fy = int(l[1])
    while True:
        rel.append(str(raw_input()))
        if rel[-1][-1] == '.':
            break
    n = len(rel)
    cal1()
else:
    n = int(l[0])
    for i in range(0, n):
        l = str(raw_input()).split(' ')
        pos.append((int(l[0]), int(l[1])))
    cal2()