Submission #76873791

---

Source Code Expand

import sys
import time
import random
from collections import deque
def openedDoor(doortype,mask):
  if doortype==-1:
    return True
  sid=doortype//2
  state=(mask>>sid) & 1
  if state==(doortype%2):
    return True
  else:
    return False
def calc_score_dist(n,k,grid,vert_doors,hori_doors,swit):
  total_states=1<<k
  dist=[[[-1]*n for _ in range(n)] for _ in range(total_states)]
  queue=deque()
  queue.append((0,0,0))
  dist[0][0][0]=0
  dirn=[[-1,0],[1,0],[0,-1],[0,1]]
  while queue:
    mask,row,col=queue.popleft()
    curr=dist[mask][row][col]
    if row==n-1 and col==n-1:
      return curr
    for r,c in dirn:
      new_r=row+r
      new_c=col+c
      if not (0<=new_r<n and 0<=new_c<n):
        continue
      if grid[new_r][new_c]=='#':
        continue
      doortype=-1
      if r==1:
        doortype=vert_doors[row][col]
      elif r==-1:
        doortype=vert_doors[new_r][new_c]
      elif c==1:
        doortype=hori_doors[row][col]
      else:
        doortype=hori_doors[new_r][new_c]
      if not openedDoor(doortype,mask):
        continue
      if dist[mask][new_r][new_c]==-1:
        dist[mask][new_r][new_c]=curr+1
        queue.append((mask,new_r,new_c))
    swittype=swit[row][col]
    if swittype!=-1:
      next_mask=mask^(1<<swittype)
      if dist[next_mask][row][col]==-1:
        dist[next_mask][row][col]=curr+1
        queue.append((next_mask,row,col))
  return 0
  
def solve():
  start_time=time.time()
  limit=1.85
  data=sys.stdin.read().split()
  if not data:
    return
  n=int(data[0])
  max_doors=int(data[1])
  k=int(data[2])
  grid=data[3:3+n]
  empty_cells=[]
  for i in range(n):
    for j in range(n):
      if grid[i][j]=='.':
        empty_cells.append([i,j])
  vert_doors=[[-1]*n for i in range(n)]
  hori_doors=[[-1]*n for i in range(n)]
  swit=[[-1]*n for i in range(n)]
  placed_doors=[]
  placed_swit=[]
  cand_pos=[]
  for i,j in empty_cells:
    if [i,j]==[0,0]:
      continue
    if [i,j]==[n-1,n-1]:
      continue
    cand_pos.append([i,j])
  random.shuffle(cand_pos)
  for sid in range(k):
    if sid>=len(cand_pos):
      break
    i,j=cand_pos[sid]
    swit[i][j]=sid
    placed_swit.append([i,j,sid])
  currtype=0
  for i in range(n-1):
    for j in range(n):
      if len(placed_doors)>=max_doors//2:
        break
      if grid[i][j]!='.':
        continue
      if grid[i+1][j]!='.':
        continue
      vert_doors[i][j]=currtype
      placed_doors.append([0,i,j,currtype])
      currtype=(currtype+1)%(2*k)
  best_dist=calc_score_dist(n,k,grid,vert_doors,hori_doors,swit)
  while True:
    elapsed=time.time()-start_time
    if elapsed>limit:
      break
    if placed_swit and random.random()<0.30:
      move_switch=True
    else:
      move_switch=False
    if move_switch:
      switch_index=random.randrange(len(placed_swit))
      old_r,old_c,swit_type=placed_swit[switch_index]
      new_r,new_c=random.choice(cand_pos)
      if swit[new_r][new_c]!=-1:
        continue
      swit[old_r][old_c]=-1
      swit[new_r][new_c]=swit_type
      cand_score=calc_score_dist(n,k,grid,vert_doors,hori_doors,swit)
      if cand_score>best_dist:
        best_dist=cand_score
        placed_swit[switch_index]=[new_r,new_c,swit_type]
      else:
        swit[new_r][new_c]=-1
        swit[old_r][old_c]=swit_type
    elif placed_doors:
      door_index=random.randrange(len(placed_doors))
      dirn,row,col,old_type=placed_doors[door_index]
      new_type=random.randint(0,2*k-1)
      if dirn==0:
        vert_doors[row][col]=new_type
      else:
        hori_doors[row][col]=new_type
      cand_score=calc_score_dist(n,k,grid,vert_doors,hori_doors,swit)
      if cand_score>best_dist:
        best_dist=cand_score
        placed_doors[door_index]=[dirn,row,col,new_type]
      else:
        if dirn==0:
          vert_doors[row][col]=old_type
        else:
          hori_doors[row][col]=old_type
  print(len(placed_doors))
  for dirn,row,col,door_type in placed_doors:
    print(dirn,row,col,door_type)
  print(len(placed_swit))
  for row,col,stype in placed_swit:
    print(row,col,stype)
solve()
  

Submission Info

Judge Result