17135.城の防御


質問リンク
17135.城の防御
問題コード
from itertools import combinations
from collections import deque
import copy
row,col,D = list(map(int,input().split()))

original_board = [[0 for c in range(col)]for r in range(row)]

comb_list = []

for i in range(col):
    comb_list.append(i)

archor_list = list(combinations(comb_list,3))

#print(archor_list)

for i in range(row):
    num_list = list(map(int,input().split()))
    for j in range(col):
        original_board[i][j] = num_list[j]

#print(board)

max_count = 0

for archors in archor_list:
    board = copy.deepcopy(original_board)
    kill = []
    count = 0

    for tot in range(row):
        for archor in archors:
            start = [row-1,archor]

            que = deque()

            que.append([start[0],start[1],1])
            visited = [[0 for c in range(col)]for r in range(row)]
            while len(que)>0:
                x,y,distance = que.popleft()

                if distance > D:
                    break
                if board[x][y] == 1:
                    kill.append([x,y])
                    break
                visited[x][y] = 1

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

                for i in range(3):
                    next_x = x+dx[i]
                    next_y = y+dy[i]

                    if 0<=next_x<row and 0<=next_y<col and visited[next_x][next_y] == 0:
                        que.append([next_x,next_y,distance+1])

        #print(kill)
        for die in kill:
            x,y = die
            if board[x][y] == 1:
                count+=1
                board[x][y]=0
        kill =[]
        #print(board, count)

        for i in range(row-1,0,-1):
            for j in range(col):
                board[i][j] = board[i-1][j]

        for j in range(col):
            board[0][j] = 0

        #print(board)

    max_count = max(max_count,count)


print(max_count)
問題を解く
  • 初回試行
  • の例はすべて正しいが、コミットすると
  • が間違っている.
  • 反例1号には6つの答えがあります
  • Killlistが初期化されていないことによる問題を特定する
  • 部分解決合格
  • 反例
    2 4 2
    1 1 1 1
    0 1 1 0
    answer :5