Submission #144945

---

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 solve(R, C, K, F):
    s = findPos(F, "S")
    c = findPos(F, "C")
    g = findPos(F, "G")

    NOWAY = 1000000
    # [start,goal,k] = N
    def mint():
        return NOWAY
    dp = defaultdict(mint)

    def filldp(F, s, p, t, k):
        ss = [(s, p, t, k)]

        while len(ss) > 0:
            s, p, t, k = ss.pop(0)
            if k > K:
                continue
            f = False
            for kk in range(k, K+1):
                if dp[s,p,kk] > t:
                    dp[s,p,kk] = t
                    f = True
            if not f:
                continue

            px, py = p
            np = []
            if px + 1 < C:
                np.append((px + 1, py))
            if px - 1 >= 0:
                np.append((px - 1, py))
            if py + 1 < R:
                np.append((px, py + 1))
            if py - 1 >= 0:
                np.append((px, py - 1))
    
            for nx, ny in np:
                if F[ny][nx] == 'E':
                    ss.append((s, (nx, ny), t+1, k+1))
                elif F[ny][nx] != 'T':
                    ss.append((s, (nx, ny), t+1, k))

    filldp(F, s, s, 0, 0)
    filldp(F, c, c, 0, 0)
    filldp(F, g, g, 0, 0)
    
    vary = defaultdict(list)
    for y in range(R):
        for x in range(C):
            i = (x, y)
            prev = -1
            for k in range(K+1):
                if dp[s,i,k] != prev:
                    vary[s,i].append(k)
                    prev = dp[s,i,k]
            prev = -1
            for k in range(K+1):
                if dp[c,i,k] != prev:
                    vary[c,i].append(k)
                    prev = dp[c,i,k]

    m = NOWAY
    for y in range(R):
        for x in range(C):
            i = (x, y)
            for k1 in vary[s,i]:
                for k2 in vary[c,i]:
                    k3 = K - k1 - k2
                    if k3 < 0:
                        break
                    t = dp[s,i,k1] + dp[c,i,k2] * 2 + dp[g,i,k3]
                    if m > t:
                        m = t
                    #if m > t:
                    #    print x, y, k1, k2, k3, dp[s,i,k1], dp[c,i,k2], dp[g,i,k3]
    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 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 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