Submission #1174153

---

Source Code Expand

import random, sys
import time
inputs = lambda: map(int, raw_input().split())

random.seed()

h, w, k, t = inputs()
X, Y = h, w
Cars = [inputs() for i in xrange(k)]
Coms = []

com_str = "LRUD-"
dd = [(0, -1), (0, 1), (-1, 0), (1, 0), (0, 0)]
wds = {(0, 0): [1, 2], (1, 0): [2, 0], (0, 1): [3, 1], (1, 1): [0, 3]}

order = range(k)
ds = range(4)

pre = 600

def dist(x0, y0, x1, y1):
    return abs(x0 - x1) + abs(y0 - y1)
def calc_score(L, Cars):
    Pd = 20 + sum(abs(x0 - x1) + abs(y0 - y1) for x0, y0, x1, y1 in Cars)
    Pt = 10 + L * 0.01
    return 10**7 / (Pt * Pd)

X2 = X/2
Y2 = Y/2
L = 0
tries = 10
last = -1
for l in xrange(t):
    update = 0
    current_score = calc_score(l, Cars)
    #print Cars, current_score
    next_score = 0 if l < pre else current_score
    coms = [4]*k
    exist_ = {(x0, y0) for x0, y0, x1, y1 in Cars}
    for _ in xrange(tries if l >= pre and last == -1 else 1):
        coms_tmp = [4]*k
        nCars = [e[:] for e in Cars]
        random.shuffle(order)
        exist = set(exist_)
        for i in order:
            x0, y0, x1, y1 = Cars[i]
            #if x0 == x1 and y0 == y1:
            #    continue

            if (l < pre and abs(x0 - y0) + abs(x1 - y1) > 3) or last != -1:
                random.shuffle(ds)
                wild = random.randint(0, 1) and last == -1
                for d in ds:
                    dx, dy = dd[d]
                    nx = x0 + dx; ny = y0 + dy
                    if not 0 < nx <= X or not 0 < ny <= Y:
                        continue
                    if not wild and dist(x0, y0, x1, y1) <= dist(nx, ny, x1, y1):
                        continue
                    if (nx, ny) not in exist:
                        update = 1
                        exist.add((nx, ny))
                        nCars[i] = (nx, ny, x1, y1)
                        coms_tmp[i] = d
                        break
            else:
                dds = wds[((x0-1)/X2, (y0-1)/Y2)]
                for d in dds if random.randint(0, 1) else reversed(dds):
                    dx, dy = dd[d]
                    nx = x0 + dx; ny = y0 + dy
                    if 0 < nx <= X and 0 < ny <= Y:
                        if (nx, ny) not in exist:
                            update = 1
                            exist.add((nx, ny))
                            nCars[i] = (nx, ny, x1, y1)
                            coms_tmp[i] = d
                            break
                else:
                    random.shuffle(ds)
                    for d in ds:
                        dx, dy = dd[d]
                        nx = x0 + dx; ny = y0 + dy
                        if not 0 < nx <= X or not 0 < ny <= Y:
                            continue
                        if (nx, ny) not in exist:
                            update = 1
                            exist.add((nx, ny))
                            nCars[i] = (nx, ny, x1, y1)
                            coms_tmp[i] = d
                            break

        score = calc_score(l+1, nCars)
        if next_score < score:
            next_score = score
            coms = coms_tmp
    if l > pre and (current_score == next_score or l == 10000):
        if last == -1:
            last = 100
        elif last == 0 or (update == 0 and last > 0):
            L = l
            break
    for i in xrange(k):
        dx, dy = dd[coms[i]]
        x0, y0, x1, y1 = Cars[i]
        Cars[i] = (x0+dx, y0+dy, x1, y1)
    Coms.append(map(com_str.__getitem__, coms))
    if last > 0:
        last -= 1
sys.stdout.write("%d\n" % L)
sys.stdout.write("\n".join("".join(e) for e in Coms))

Submission Info

Judge Result