Submission #68711329

---

Source Code Expand

import bisect, heapq, sys, math, copy, itertools, decimal
from collections import defaultdict, deque
import pprint
sys.setrecursionlimit(10**7)
def INT(): return int(input())
def MI(d=0): return map(lambda x:int(x)+d, input().split())
def MS(): return map(str, input().split())
def LI(d=0): return list(map(lambda x:int(x)+d, input().split()))
def LS(): return list(map(str, input().split()))
def pr_line(itr): print(*itr, sep='\n')
def pr_mtx(matrix): [print(*row) for row in matrix] 
def pr_mtx2(matrix, l=2):
    for row in matrix:
        for x in row:
            print(str(x).rjust(l), end='')
        print('\n')
def pr_stderr(*s): print(*s, file=sys.stderr)

dij = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dij2 = [[1, 0], [0, 1], [-1, 0], [0, -1], [1, 1], [1, -1], [-1, 1], [-1, -1]]
INF = float('inf')
import random

random.seed(1234)

from time import time
base_ms = 0
def tic():
    global base_ms
    base_ms = time()

def toc():
    now = time()
    return (now - base_ms) * 1000

tic()
###########################################################

N, M, K = MI()
Robots_Pos = [LI() for _ in range(M)]
V = [list(map(int, list(input()))) for _ in range(N)]
H = [list(map(int, list(input()))) for _ in range(N-1)]
ULDRS = ['U', 'L', 'D', 'R', 'S']
###########################################################
def output(C, A):
    for c in C:
        print(*c)
    pr_line(A)

def culc_score(A):
    return 3*N**2 - len(A)


def execute(assign, C):
    robots_pos = copy.deepcopy(Robots_Pos)

    A = []
    ###########################################################
    
    Visited = set()
    for i, j in robots_pos:
        Visited.add((i, j))
    ###########################################################

    def move_one_robot(pos, move):
        i, j = pos

        if move == "U":
            if i > 0 and H[i-1][j] == 0:  
                i -= 1
        elif move == "D":
            if i < N-1 and H[i][j] == 0:  
                i += 1
        elif move == "L":
            if j > 0 and V[i][j-1] == 0:  
                j -= 1
        elif move == "R":
            if j < N-1 and V[i][j] == 0:  
                j += 1
        elif move == "S":
            pass  
        
        Visited.add((i, j))
        return (i, j)

    def move_all_robot(k_operation):
        for i in range(M):
            pos = robots_pos[i]
            move = C[k_operation][i]
            ni, nj = move_one_robot(pos, move)
            robots_pos[i] = [ni, nj]
        A.append(k_operation)

    def judge_wall(move, pos):
        i, j = pos
        if move == "U" and H[i-1][j] == 1: return False
        if move == "D" and H[i][j]   == 1: return False
        if move == "L" and V[i][j-1] == 1: return False
        if move == "R" and V[i][j]   == 1: return False
        return True

    def nxt_pos(i, j, move):
        if move == "U": i -= 1
        if move == "D": i += 1
        if move == "L": j -= 1
        if move == "R": j += 1
        return i, j

    visited = [[-1]*N for _ in range(N)]
    def dfs(i, j, d):
        if len(Visited) == N*N: return 0
        
        visited[i][j] = d
        
        flag = False
        for k_ in range(K):
            k = (k_ + 4*(d%2))%8
            if len(Visited) == N*N: return 0
            move = C[k][assign]
            pos = (i, j)
            ni, nj = nxt_pos(i, j, move)
            if 0<=ni<N and 0<=nj<N and (ni, nj) and visited[ni][nj] == -1:
                if not judge_wall(move, pos):
                    continue
                flag = True
                move_all_robot(k)
                #pr_stderr('Visited:', len(Visited))
                done = dfs(ni, nj, d+1)
                if len(Visited) == N*N: return 0
                
                # #行き止まりだった場合は戻らず距離の近い所へ行く
                # if not done:
                #     mn, mnk = INF, -1
                move_all_robot((k+2)%K)
        
        return flag

    dfs(*robots_pos[assign], 0)
    
    return A

def assigned_C(assign):
    C = [['S']*M for _ in range(K)]
    for k in range(K):
        C[k][assign] = ULDRS[k%4]
    return C

def random_C(assign):
    C = [['S']*M for _ in range(K)]
    for k in range(K):
        C[k][assign] = ULDRS[k%4]
        for i in range(M):
            if i != assign:
                C[k][i] = random.choice(ULDRS)
    return C

def select():
    mx_score = 0
    mx_id = -1
    resC, resA = -1, -1
    for i in range(M):
        C = assigned_C(i)
        A = execute(i, C)
        score = culc_score(A)
        if mx_score < score:
            mx_score = score
            mx_id = i
            resC, resA = C, A
    return resC, resA, mx_id

def nxt(C, assign_id):
    k = random.choice(range(K))
    i = random.choice([x for x in range(M) if x != assign_id])
    pre_move = C[k][i]
    C[k][i] = random.choice([move for move in ULDRS if move != pre_move])
    return k, i, pre_move

def back(C, k, i, pre_move):
    C[k][i] = pre_move

def hill_climb():
    _, _, assign_id = select()
    
    solC = random_C(assign_id) # 初期解
    solA = execute(assign_id, solC)
    solScore = culc_score(solA)
    cnt = 0
    while toc() <= 1500:
        cnt += 1
        k, i, pre_move = nxt(solC, assign_id)
        canA = execute(assign_id, solC)
        canScore = culc_score(canA)
        if canScore > solScore:
            solA = canA
            solScore = canScore
        else:
            back(solC, k, i, pre_move)

    pr_stderr('cnt:', cnt)
    return solC, solA
###########################################################
def solve():
    
    resC, resA = hill_climb()

    pr_stderr('score:', culc_score(resA))
    output(resC, resA)

if __name__ == "__main__":
    solve()

Submission Info

Judge Result