Submission #148465

---

Source Code Expand

#!/usr/bin/env python2.7

import sys
from collections import defaultdict

from cStringIO import StringIO
import unittest
import cProfile

def main():
    R, C, K = (int(x) for x in sys.stdin.readline().split())
    F = []
    for _ in range(R):
        f, = [x for x in sys.stdin.readline().split()]
        F.append(f)
    print solve(R, C, K, F)

def findPos(F, c):
    for y, l in enumerate(F):
        for x, t in enumerate(l):
            if t == c:
                return x, y

def nextpos(x, y):
    yield x+1, y
    yield x, y+1
    yield x-1, y
    yield x, y-1

NOWAY = 1000000

def calcdp(F, K, s):
    R = len(F)
    C = len(F[0])
    Es = []
    for y in range(R):
        for x in range(C):
            if F[y][x] == 'E':
                Es.append((x,y))

    dp = []

    nn = [(0, s)]
    dd = [[NOWAY for _ in range(C)] for _ in range(R)]

    for k in range(K+1):
        while len(nn) > 0:
            (t, (px, py)) = nn.pop(0)
            if dd[py][px] <= t:
                continue
            dd[py][px] = t
            for nx, ny in nextpos(px, py):
                c = F[ny][nx]
                if c != 'T' and c != 'E':
                    nn.append((t+1, (nx, ny)))
        dp.append(dd)
        dd = [[dd[y][x] for x in range(C)] for y in range(R)]
        for ex, ey in Es:
            t = min([dd[y][x] for x, y in nextpos(ex, ey)]) + 1
            if t < dd[ey][ex]:
                nn.append((t, (ex, ey)))
        nn.sort()

    return dp


def solve(R, C, K, F):
    R += 2
    C += 2
    F = ["T" * C] + [["T"] + list(l) + ["T"] for l in F] + ["T" * C]

    s = findPos(F, "S")
    c = findPos(F, "C")
    g = findPos(F, "G")

    dps = calcdp(F, K, s)
    dpc = calcdp(F, K, c)
    dpg = calcdp(F, K, g)
    
    m = NOWAY
    for y in xrange(R):
        for x in xrange(C):
            t = F[y][x] == 'E'
            for k1 in xrange(K + 1):
                if k1 != 0 and dps[k1-1][y][x] == dps[k1][y][x]:
                    continue
                for k2 in xrange(K + 1):
                    k3 = K - k1 - k2 + t * 2
                    if k3 < 0 or K < k3:
                        continue
                    d = dps[k1][y][x] + dpc[k2][y][x] * 2 + dpg[k3][y][x]
                    if d < m:
                        m = d
    if m == NOWAY:
        return -1
    return m
    
class Test(unittest.TestCase):

    @staticmethod
    def tryone(indata):
        sys.stdin = StringIO(indata)
        out = sys.stdout = StringIO()
        main()
        return out.getvalue()

    def test20(self):
        self.assertEqual(calcdp([
            "TTTTTTT",
            "T.T.E.T",
            "T.E.T.T",
            "TTTTTTT",
            ], 2, (1,1)),
            [[
                [NOWAY, NOWAY, NOWAY, NOWAY, NOWAY, NOWAY, NOWAY, ],
                [NOWAY,     0, NOWAY, NOWAY, NOWAY, NOWAY, NOWAY, ],
                [NOWAY,     1, NOWAY, NOWAY, NOWAY, NOWAY, NOWAY, ],
                [NOWAY, NOWAY, NOWAY, NOWAY, NOWAY, NOWAY, NOWAY, ],
            ],[
                [NOWAY, NOWAY, NOWAY, NOWAY, NOWAY, NOWAY, NOWAY, ],
                [NOWAY,     0, NOWAY,     4, NOWAY, NOWAY, NOWAY, ],
                [NOWAY,     1,     2,     3, NOWAY, NOWAY, NOWAY, ],
                [NOWAY, NOWAY, NOWAY, NOWAY, NOWAY, NOWAY, NOWAY, ],
            ],[
                [NOWAY, NOWAY, NOWAY, NOWAY, NOWAY, NOWAY, NOWAY, ],
                [NOWAY,     0, NOWAY,     4,     5,     6, NOWAY, ],
                [NOWAY,     1,     2,     3, NOWAY,     7, NOWAY, ],
                [NOWAY, NOWAY, NOWAY, NOWAY, NOWAY, NOWAY, NOWAY, ],
            ]])

    def test30(self):
        self.assertEqual(findPos([
            "GET..ET",
            "..T....",
            ".TEST..",
            ".E.T.ET",
            "...ETC.",
        ], "S"), (3,2))

    def test50(self):
        self.assertEqual(solve(5, 7, 3, [
            "GET..ET",
            "..T....",
            ".TEST..",
            ".E.T.ET",
            "...ETC.",
        ]), 19)

    def test80(self):
        solve(50, 50, 100, 
            ["S................................................."] +
            [".................................................."] * 48 +
            ["C................................................G"]
        )

    def test81(self):
        F = ["S................................................."];
        for _ in range(24):
            F.append("EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE.")
            F.append("..................................................")
        F.append("C................................................G")
        solve(50, 50, 100, F)

    def test91(self):
        self.assertEqual(self.tryone("""\
5 7 3
GET..ET
..T....
.TEST..
.E.T.ET
...ETC.
"""), """19\n""")

    def test92(self):
        self.assertEqual(self.tryone("""\
5 7 2
GET..ET
..T....
.TEST..
.E.T.ET
...ETC.
"""), """21\n""")

    def test93(self):
        self.assertEqual(self.tryone("""\
5 7 1
GET..ET
..T....
.TEST..
.E.T.ET
...ETC.
"""), """-1\n""")

    def test94(self):
        self.assertEqual(self.tryone("""\
6 35 4
T...TT.....TT...TTT...TTT..TTG.....
..T..T.TTT.T..T..E..T..E...TTT.TTT.
.TTT.T.....E.TTTTT.TTT.TTT.TTT.....
.....T.TT.TT.TTTTT.TTT.TTT.TTTTTTT.
.TTT.T.TT..T..T..S..T..TTT.TTTTTTT.
.CTT.E.TTT.TT...TTT...TT.....E.....
"""), """94\n""")

if __name__ == '__main__':
    if len(sys.argv) > 1:
        print "_/" * 30 + str(sys.argv)
        if sys.argv[1] == '-p':
            sys.argv.pop(1)
            cProfile.run("unittest.main(exit=False, failfast=True)", sort='time')
        else:
            unittest.main()
    else:
        main()

Submission Info

Judge Result