Submission #1204394

---

Source Code Expand

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()


def main():
    start = time.time()
    d = {'R': (0,1), 'L': (0,-1), 'U': (-1,0), 'D': (1,0)}
    dl = list(d.items())
    h,w,k,sr,sc = LI()
    b = []
    o = []
    for _ in range(h):
        s = S()
        b.append([0 if c=='.' else -1 for c in s])
        o.append([0 for _ in s])
    n = II()
    bd = {}
    for _ in range(n):
        r,c,f,g = LI()
        b[r-1][c-1] = f
        o[r-1][c-1] = g
        bd[(r-1,c-1)] = _
    s = ""
    rc = [sr-1,sc-1]
    ii = [2**i for i in range(n)]
    bi = 2**n-1

    ss = [None for _ in range(k)]
    ss[0] = (0,(sr-1,sc-1),bi,'')

    def search(t):
        f = [[False]*w for _ in range(h)]
        s,(i,j),bi,sst = ss[t]
        if bi < 1:
            return t
        q = [(s,i,j)]
        f[i][j] = '-'
        nq = []
        ck = t
        while q:
            s,r,c = q[0]
            for nk, (dr,dc) in dl:
                nr,nc = r+dr, c+dc
                if b[nr][nc] < 0 or f[nr][nc]:
                    continue
                if b[nr][nc] == 0 or not (bi & ii[bd[(nr,nc)]]):
                    nq.append((s,nr,nc,nk))
                    continue
                ns = s + b[nr][nc] - o[nr][nc] * (ck+1)
                if ss[ck+1] and ss[ck+1][0] >= ns:
                    continue

                nb = bi - ii[bd[(nr,nc)]]
                f[nr][nc] = nk
                ct = nk
                mi,mj = nr,nc
                st = ''
                while ct != '-':
                    st = ct + st
                    mi,mj = mi-d[ct][0], mj-d[ct][1]
                    ct = f[mi][mj]
                ss[ck+1] = (ns,(nr,nc),nb,st)
            q = q[1:]
            if not q and ck < k-2:
                ck += 1
                for ns,nr,nc,nk in nq:
                    if f[nr][nc]:
                        continue
                    q.append([ns,nr,nc])
                    f[nr][nc] = nk

        # if t == 0 and False:
        #     print(ss[3])
        #     print('\n'.join(''.join(c if c else '.' for c in fr) for fr in f))
        return t

    mc = 0
    mi = -1
    for ki in range(k):
        if not ss[ki]:
            continue
        if mi+100 < ki:
            break
        if ss[ki][0] > mc:
            mc = ss[ki][0]
            mi = ki
        search(ki)

    sys.stderr.write('\n'.join(map(lambda x: str(x[0]), [c for c in ss[:10] if c])))
    sys.stderr.write('mi: {}, mc: {}\n'.format(mi, mc))

    r = ''
    rd = set()
    while mi > 0:
        r = ss[mi][3] + r
        rd.add(ss[mi][1])
        mi -= len(ss[mi][3])
        # if mi < 10 and False:
        #     sys.stderr.write('mi: {}, mc: {}, ss: {}\n'.format(mi, ss[mi][0], ss[mi][1]))

    def score(r):
        bd = copy.deepcopy(b)
        t = (sr-1,sc-1)
        rc = 0
        for i in range(len(r)):
            c = r[i]
            if c == '-':
                break
            nr,nc = d[c][0] + t[0], d[c][1] + t[1]
            if bd[nr][nc] == -1:
                print('error.', nr,nc,i,c)
                return False
            if bd[nr][nc] > 0:
                rc += bd[nr][nc] - o[nr][nc] * (i+1)
            t = (nr,nc)
        return rc

    # print(score(r))
    print((r + '-'*k)[:k])
    # sys.stderr.write("time:{0} sec\n".format(time.time() - start))

main()

Submission Info

Judge Result