白駿2146号造橋

白駿2146号造橋

問題のショートカット

トラブルシューティング

💣 bfsを用いた最小距離完全ナビゲーションの方法

この問題は、各領域から別の領域までの最短距離を求めることです.
この問題を解決するには、各領域が互いに独立している必要があります.

import sys
from collections import deque

def splitGround():
  numbering = 2
  for i in range(N):
    for j in range(N):
      if board[i][j] != 1:
        continue 
      deq = deque()
      deq.append([i, j])
      board[i][j] = numbering
      while deq:
        r, c = deq.popleft()
        for v in range(4):
          newRow = r + dy[v]
          newColumn = c + dx[v]

          if newRow < 0 or newRow >= N or newColumn < 0 or newColumn >= N:
            continue

          if board[newRow][newColumn] == 1:
            board[newRow][newColumn] = numbering
            deq.append([newRow, newColumn])
      
      numbering += 1
  return numbering

def calculateMinDistance(countGround):  
  minDistance = 100001
  distDictionary = {count : [[0 for i in range(N)] for v in range(N)] for count in range(2, countGround)}
  for i in range(N):
    for j in range(N):
      if board[i][j] == 0:
        continue 
      
      deq = deque()
      deq.append([i, j])
      number = board[i][j]
      distBoard = distDictionary[number]
      while deq:
        r, c = deq.popleft()
        dist = distBoard[r][c]
        for v in range(4):
          newRow = r + dy[v]
          newColumn = c + dx[v]

          if newRow < 0 or newRow >= N or newColumn < 0 or newColumn >= N:
            continue

          if board[newRow][newColumn] == 0:
            if distBoard[newRow][newColumn] == 0:
              distBoard[newRow][newColumn] = dist + 1
              deq.append([newRow, newColumn])

            if distBoard[newRow][newColumn] > dist + 1:
              distBoard[newRow][newColumn] = dist + 1
              deq.append([newRow, newColumn])
          else:          
            if board[newRow][newColumn] != number:
              minDistance = min(minDistance, dist)
              break

  return minDistance

N = int(sys.stdin.readline())
board = []

for i in range(N): 
  board.append(list(map(int, sys.stdin.readline().split())))

dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]

countGround = splitGround()

print(calculateMinDistance(countGround))

Boardスキームを作成し、各領域に異なる番号を追加しました.

完全ナビゲーションにより、各出発点から他の領域までのすべての距離を求め、最高値を返す.

で訪問した海域(0)にマークが付けられていない場合、繰返し計算が発生する可能性があります.

したがって、距離を表す新しい配列distBoardを作成し、各領域ごとに別の領域への距離を格納し、計算の重複を回避します.最初に、私たちは以下の方法で問題を解決しました.しかし,各パーティションは異なる距離値を格納しなければならないため,distdictionaryとdistBoard配列のパーティション格納方法を用いた.
結果は?
メモリオーバーフロー
スコアリング後、100 x 100サイズの配列を複数の異なる配列に分割すると、メモリが過剰に使用されるに違いありません.ほほほ

再帰関数を用いて解く

import sys
from collections import deque

def splitGround():
  numbering = 2
  for i in range(N):
    for j in range(N):
      if visited[i][j] != 1:
        continue 
      deq = deque()
      deq.append([i, j])
      visited[i][j] = numbering
      while deq:
        r, c = deq.popleft()
        for v in range(4):
          newRow = r + dy[v]
          newColumn = c + dx[v]

          if newRow < 0 or newRow >= N or newColumn < 0 or newColumn >= N:
            continue

          if visited[newRow][newColumn] == 1:
            visited[newRow][newColumn] = numbering
            deq.append([newRow, newColumn])
      
      numbering += 1

def calculateMinDistance(depth):
  dist = 100001
  for r in range(N):
    for c in range(N):
      if board[r][c] != depth:
        continue 
      numbering = visited[r][c]
      for v in range(4):
        newRow = r + dy[v]
        newColumn = c + dx[v]

        if newRow < 0 or newRow >= N or newColumn < 0 or newColumn >= N:
          continue

        if board[newRow][newColumn] == 0:
          board[newRow][newColumn] = depth + 1
          visited[newRow][newColumn] = numbering
        if board[newRow][newColumn] == depth and visited[newRow][newColumn] != numbering:
          dist = min(dist, (depth-1) * 2)
          
        if board[newRow][newColumn] == depth-1 and visited[newRow][newColumn] != numbering:
          dist = min(dist, board[newRow][newColumn] + depth -2)
  if dist != 1001:
    return dist
  return calculateMinDistance(depth + 1)
N = int(sys.stdin.readline())
board = []
visited = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N): 
  board.append(list(map(int, sys.stdin.readline().split())))

for i in range(N):
  for j in range(N):
    if board[i][j] == 1:
      visited[i][j] = 1 

dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]

splitGround()
print(calculateMinDistance(1))

メモリオーバーフローの解決方法を変更しました.
bfsの使用と比較して,各領域で再帰関数を使用し,各重複再帰関数で領域を拡張する方法を採用した.

boardは、距離を表すために2つのvistive配列を使用し、board配列では領域を分割せず、領域を1格子広くします.

領域を展開すると、他の領域に遭遇すると、2つの領域を接続するブリッジの大きさが得られます.

は、これが異なる領域であることを知る必要があるため、vistive配列を使用するたびに、自分の領域であることを番号で表す.

役に立つ反例

5
1 0 0 0 0
1 0 0 0 1
1 1 1 0 1
0 0 0 0 0
0 0 0 1 0

정답: 1

5
1 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 0 0 1

정답: 2