boj 14502研究所(金貨5)

boj 14502研究所
これもサムスン基出!
bfsベースのようですが、3つの壁を選択して建てる必要があるので、追加の処理が必要です.
与えられた地図では、0の中から3つの場所を選んで壁を立て、どこに建てるのが一番いいのかを少し考えて、「すべての場合に立てるべき数だ」と結論付けた.
与えられた地図の最大サイズは8*8で、完全に探してみるのもいいです.
おおよそ計算すると、64 C 3=約4万、与えられたbfsの場合、すべての地図を閲覧するには、最大8*8、最大64回以内なので、60回ぐらいかかりますが、どれだけ生きているかチェックしたいなら、60回ぐらいかかります.
4万*60*60=約1億いくらですか?
Pythonは遅いので、一秒で2千万くらいは取れるかと思います.
まず方法が思いつかなかったので,このように編んでみた.
list(itertools.permutation(arr,n))
これは配列の中でn個の組み合わせをリストに編成する方法です!
import itertoolsと一緒に使えばいいです.
itertoolsのシーケンスと組合せ関数は何度か使ったことがありますが、本当にたまに使ったことがあるかもしれないので、あまり詳しくありません.検索できなければ使えない...
もしあなたが覚えていないなら、私たちは直接n重砲門で関数を作るべきだと思います.

import itertools
import copy
from collections import deque

n,m = map(int,input().split())
dy = [0,1,0,-1]
dx = [1,0,-1,0]
answer_list = []

first_state = [list(map(int,input().split())) for _ in range(n)]

arr = []

for i in range(n):
  for j in range(m):
    if first_state[i][j] == 0:
      arr.append((i,j))

wall_list = list(itertools.permutations(arr,3))

def collision(state):
  global n,m
  state = state
  queue = deque()
  for i in range(n):
    for j in range(m):
      if state[i][j] == 2 :
        queue.append((i,j))
        while(queue):
          y,x = queue.popleft()
          for k in range(4):
            ny = y + dy[k]
            nx = x + dx[k]

            if ny <0 or nx < 0 or ny >=n or nx >=m:
              continue

            if state[ny][nx] == 0:
              state[ny][nx] = 2
              queue.append((ny,nx))

  return state

def safecheck(state):
  global n,m
  count = 0
  for i in range(n):
    for j in range(m):
      if state[i][j] == 0:
        count += 1

  return count

for wall in wall_list:
  # state = first_state
  state = copy.deepcopy(first_state)
  state[wall[0][0]][wall[0][1]] = 1
  state[wall[1][0]][wall[1][1]] = 1
  state[wall[2][0]][wall[2][1]] = 1
  state = collision(state)
  answer_list.append(safecheck(state))


print(max(answer_list))
   

振り返る

全部編んで、結局ずっとゼロで、印刷物で段階的に印刷して、場所を間違えました
問題は配列のコピーです.
問題は、以下に注記するstate=first state部分です.
Pythonはこのようにコピーすれば、callbyreferenceにアドレス値をコピーし、stateに触れるとfirst stateも変化します.
アドレスではなく値だけをコピーする場合はdeelcopyを使用します.
import copyを提供してください
b = copy.deepcopy(a)
このような処理により,一般値を任意にコピーすることができる.
今学期、コンピュータービジョンチームがコードを書いたとき、間違った場所を探すために長い時間がかかりました.久しぶりに見ましたが、思いもよらなかったです.
c++の使用に慣れているため、Pythonはいつも配列コピーを参考にしていません.
必ず覚えておいてください.

結果

Pythonを回すとタイムアウトになります
しかし、三星珂太氏は、スコアサーバがPyPy 3環境で稼働しているのは正しいと述べた.
Pythonでも通れるもっと早い方法を検討します.
終わりだ!