#2327636

Solution for 1144: Curling 2.0 by n_knuu

Source Code Status Test Cases
    Policy: public     Reviewed: 3    
40.00 sec    215548 KB    52 lines     1539 bytes    2017-05-20 05:20
import collections
import copy
import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input
drc = [(0, -1), (1, 0), (0, 1), (-1, 0)]


def in_board(r, c):
    return 0 <= r < H and 0 <= c < W


while True:
    W, H = map(int, input().split())
    if not (W | H):
        break
    origin_board = [[int(x) for x in input().split()] for _ in range(H)]
    sr, sc, gr, gc = 0, 0, 0, 0
    for r in range(H):
        for c in range(W):
            if origin_board[r][c] == 2:
                sr, sc = r, c
                origin_board[sr][sc] = 0
            elif origin_board[r][c] == 3:
                gr, gc = r, c
    memo = dict()
    que = collections.deque([(sr, sc, origin_board, 0)])
    while que:
        r, c, board, cnt = que.popleft()
        if (r, c) == (gr, gc):
            print(cnt)
            break
        for i, (dr, dc) in enumerate(drc):
            nr, nc = r + dr, c + dc
            if (r, c, i) in memo:
                nr, nc = memo[r, c, i]
            if in_board(nr, nc) and board[nr][nc] != 1:
                next_board = copy.deepcopy(board)
                while in_board(nr, nc) and board[nr][nc] == 0:
                    nr += dr
                    nc += dc
                if in_board(nr, nc) and cnt < 10:
                    if next_board[nr][nc] == 1:
                        next_board[nr][nc] = 0
                        nr, nc = nr - dr, nc - dc
                    memo[r, c, i] = nr, nc
                    que.append((nr, nc, next_board, cnt + 1))

    else:
        print(-1)


Compile Error Logs:
You are not authorized to see the message.

Status
Judge: 0/1 Python CPU: 40.00 sec Memory: 215548 KB Length: 1539 B 2017-05-20 05:20 2017-05-20 05:21
Results for testcases
Case # Verdict CPU Time Memory In Out Case Name
Case #1: : Time Limit Exceeded 20.00 sec 215548 KB
< prev | / | next >  
 
Judge Input #  ( | ) Judge Output #  ( | )


Comments
 
 Under Construction.
 
Categories
 
 
Free Tags