Submission #1174338


Source Code Expand

# -*- coding: utf-8 -*-
import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll, random

def print_board():
    for y in xrange(Y):
        line = ""
        for x in xrange(X):
            line += "#" if board[y][x] else "-"
        print line
    print
    sys.stdout.flush()
            
def is_inside(x, y):
    return 0 <= y < Y and 0 <= x < X

dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]]

Y, X, K, T = map(int, raw_input().split())
car = [map(int, raw_input().split()) for i in xrange(K)]
for i, (y, x, gy, gx) in enumerate(car):
    car[i] = [y - 1, x - 1, gy - 1, gx - 1]

board = [[False]*X for i in xrange(Y)]
for y, x, gy, gx in car:
    board[y][x] = True


def main():
    global board
    moves = []
    for loop in xrange(min(25, T)):
        #print_board()
        move = ""
        _board = copy.deepcopy(board)
        for i, (y, x, gy, gx) in enumerate(car):
            if (y, x) == (gy, gx):
                move += "-"
                continue
            order = [0, 1, 2, 3]
            order.sort(key = lambda j: abs(x + dxy[j][0] - gx) + abs(y + dxy[j][1] - gy))
            for j in order:
                dx, dy = dxy[j]
                nx, ny = x + dx, y + dy
                if not is_inside(nx, ny): continue
                if board[ny][nx]: continue
                if _board[ny][nx]: continue
                _board[ny][nx] = True
                _board[y][x] = False
                move += "RDLU"[j]
                car[i] = [ny, nx, gy, gx]
                break
            else:
                move += "-"
        board = copy.deepcopy(_board)
        moves.append(move)
        assert len(move) == 450

    print len(moves)
    for move in moves:
        print move


if __name__ == "__main__":
    main()

Submission Info

Submission Time
Task B - 日本橋大渋滞
User roiti
Language Python (2.7.6)
Score 3790
Code Size 1835 Byte
Status AC
Exec Time 109 ms
Memory 5528 KB

Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10 test_11 test_12 test_13 test_14 test_15 test_16 test_17 test_18 test_19 test_20 test_21 test_22 test_23 test_24 test_25 test_26 test_27 test_28 test_29 test_30
Score / Max Score 130 / 50000 128 / 50000 130 / 50000 129 / 50000 138 / 50000 127 / 50000 127 / 50000 133 / 50000 122 / 50000 123 / 50000 130 / 50000 125 / 50000 124 / 50000 130 / 50000 123 / 50000 134 / 50000 124 / 50000 123 / 50000 124 / 50000 126 / 50000 129 / 50000 127 / 50000 125 / 50000 125 / 50000 121 / 50000 125 / 50000 126 / 50000 116 / 50000 125 / 50000 121 / 50000
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
test_01 subtask_01_01.txt
test_02 subtask_01_02.txt
test_03 subtask_01_03.txt
test_04 subtask_01_04.txt
test_05 subtask_01_05.txt
test_06 subtask_01_06.txt
test_07 subtask_01_07.txt
test_08 subtask_01_08.txt
test_09 subtask_01_09.txt
test_10 subtask_01_10.txt
test_11 subtask_01_11.txt
test_12 subtask_01_12.txt
test_13 subtask_01_13.txt
test_14 subtask_01_14.txt
test_15 subtask_01_15.txt
test_16 subtask_01_16.txt
test_17 subtask_01_17.txt
test_18 subtask_01_18.txt
test_19 subtask_01_19.txt
test_20 subtask_01_20.txt
test_21 subtask_01_21.txt
test_22 subtask_01_22.txt
test_23 subtask_01_23.txt
test_24 subtask_01_24.txt
test_25 subtask_01_25.txt
test_26 subtask_01_26.txt
test_27 subtask_01_27.txt
test_28 subtask_01_28.txt
test_29 subtask_01_29.txt
test_30 subtask_01_30.txt
Case Name Status Exec Time Memory
subtask_01_01.txt AC 109 ms 5528 KB
subtask_01_02.txt AC 84 ms 4252 KB
subtask_01_03.txt AC 83 ms 4252 KB
subtask_01_04.txt AC 84 ms 4252 KB
subtask_01_05.txt AC 82 ms 4252 KB
subtask_01_06.txt AC 84 ms 4252 KB
subtask_01_07.txt AC 85 ms 4252 KB
subtask_01_08.txt AC 83 ms 4252 KB
subtask_01_09.txt AC 83 ms 4252 KB
subtask_01_10.txt AC 84 ms 4252 KB
subtask_01_11.txt AC 83 ms 4252 KB
subtask_01_12.txt AC 85 ms 4252 KB
subtask_01_13.txt AC 84 ms 4252 KB
subtask_01_14.txt AC 83 ms 4252 KB
subtask_01_15.txt AC 84 ms 4252 KB
subtask_01_16.txt AC 85 ms 4252 KB
subtask_01_17.txt AC 83 ms 4252 KB
subtask_01_18.txt AC 84 ms 4252 KB
subtask_01_19.txt AC 83 ms 4252 KB
subtask_01_20.txt AC 83 ms 4252 KB
subtask_01_21.txt AC 82 ms 4252 KB
subtask_01_22.txt AC 83 ms 4252 KB
subtask_01_23.txt AC 83 ms 4252 KB
subtask_01_24.txt AC 85 ms 4252 KB
subtask_01_25.txt AC 84 ms 4252 KB
subtask_01_26.txt AC 83 ms 4252 KB
subtask_01_27.txt AC 83 ms 4252 KB
subtask_01_28.txt AC 84 ms 4252 KB
subtask_01_29.txt AC 83 ms 4252 KB
subtask_01_30.txt AC 84 ms 4252 KB