제출 #1343152

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1343152		eri	Tracks in the Snow (BOI13_tracks)	Pypy 3	58.44 / 100	2151 ms	1114112 KiB

tracks

from collections import defaultdict, deque
def main():
    ncols, nrows = map(int, input().split())
    field_yx = []
    for icol in range(ncols):
        field_yx.append(tuple(input()))
    connection_graph = defaultdict(set)
    for icol in range(ncols):
        for irow in range(nrows):
            if field_yx[icol][irow] != ".":
                for direction in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                    if 0 <= icol + direction[1] < ncols and 0 <= irow + direction[0] < nrows and field_yx[icol + direction[1]][irow + direction[0]] != ".":
                        connection_graph[(icol, irow)].add(
                            ((icol + direction[1], irow + direction[0]),
                             int(field_yx[icol + direction[1]][irow + direction[0]] != field_yx[icol][irow])
                            )
                        )
    #0 - 1 BFS ; ans is longest, across all vertices, shortest path from field[0][0]
    distances = defaultdict(lambda: None)
    distances[(0, 0)] = 0
    toVisit = deque(((0, 0),))
    while toVisit:
        edge_from = toVisit.popleft()
        for edge in connection_graph[edge_from]:
            edge_to, weightOfedge_from = edge
            if distances[edge_to] is None or distances[edge_from] + weightOfedge_from < distances[edge_to]:
                distances[edge_to] = distances[edge_from] + weightOfedge_from
                if weightOfedge_from:
                    toVisit.append(edge_to)
                else:
                    toVisit.appendleft(edge_to)
    #
    print(max(distances.values()) + 1)

if __name__ == '__main__':
    main()

컴파일 시 표준 출력 (stdout) 메시지

Compiling 'tracks.py'...

=======
  adding: __main__.pyc (deflated 39%)

=======

• Subtask 1: 30 / 30
• Subtask 2: 28.4375 / 70