[BOJ]17135-城の防御


質問リンク


ガードレール

問題の説明


N*Mサイズの碁盤があり、各格に敵がいるかもしれないし、ないかもしれない.(空欄:0、敵:1)N+1行には城があり、城には3人のアーチェリー手が配置され、射程D以下の敵の中で最も近い敵を射殺した.1つの格に1人のアーチェリー手しか存在しないが、少なくとも射程の敵が2人を超えると、一番左の敵を射殺する.距離は、2つの位置(r 1、c 1)、(r 2、c 2)|r 1−r 2|+|c 1−c 2|である.
射殺された敵はスケートボードから消え、攻撃後は敵ごとに城に1つ移動する.城に着いた敵も同じようにスケートボードから消える.
定格ベゼルを与えた状態で、アーチェリーの攻撃で解消できる敵の最大数は?

問題を解く


詳細な条件は実現しにくい問題です.
3≦N,M≦153≦N,M≦153≦N,M≦15,NとMの範囲は大きくなく,組み合わせを用いて可能なすべてのアーチェリーハンド配置を調べた.
実装する必要がある条件フローは、次のとおりです.
各アーチェリーに対して配置
攻撃

  • 1.1全ての敵に対して、アーチェリー1、アーチェリー2、アーチェリー3の位置基準射程D以下の敵の中で最も近く、最も左の敵を探す.
    1.2攻撃した敵は碁盤から消し去る.
  • 移動

  • 碁盤に残った敵を城の方向に1コマ移動させる.(y軸+1)
    移動した敵が城に到着すると、スケートボードからクリアします.
  • マザーボードに敵がいないかどうかを確認します.
    敵が1人もいなければ,そのアーチェリーハンド配置状況に対して,射殺した敵のcountを全体最大値と比較更新する.
  • ここで最も厄介な実施部分はやはり細かい攻撃が多い.
    まず,敵の座標は碁盤の状態を入力する際に敵の配列に保存され,各弓手の配置に対してdeepcopyを用いて元の位置を破壊せずに碁盤から移動を排除するなどの操作を行う.
     cur_enemies = copy.deepcopy(enemies, key = lambda x : (-x[0], x[1]))
    ランキングの理由は、最短射程の敵の中から「一番左の敵」を選ぶため.ただし,抜けた条件がないかチェックせずにソートのみを行い,一番左かチェックしないとエラー^ㅠが発生する.
    敵を攻撃する部分を探して、cur敵のすべての敵に対して各アーチェリー手から敵までの距離を計算し、この値は1です.与えられた射程がD以下であるかこれまでこのアーチェリーの最小射程は3だった.少なくとも一番左の敵が正しいかどうかをチェックした.
    #1. 공격하기
            D1, D2, D3 = N+M, N+M, N+M
            enemy1, enemy2, enemy3 = [0,0], [0,0], [0,0]
            #공격할 적 찾기
            for enemy in cur_enemies:
                #현재 체크하는 적 위치~각 궁수 위치까지의 거리
                d1 = abs(N-enemy[0]) + abs(arc1-enemy[1])
                d2 = abs(N-enemy[0]) + abs(arc2-enemy[1])
                d3 = abs(N-enemy[0]) + abs(arc3-enemy[1])
    
                if D1 > d1 and d1 <= D:
                    #현재까지의 최소 거리이면
                    D1 = d1
                    enemy1 = enemy
                elif D1 == d1 and d1 <= D:
                    if enemy1[1] > enemy[1]:
                        D1 = d1
                        enemy1 = enemy
                if D2 > d2 and d2 <= D:
                    #현재까지의 최소 거리이면
                    D2 = d2
                    enemy2 = enemy
                elif D2 == d2 and d2 <= D:
                    if enemy2[1] > enemy[1]:
                        D2 = d2
                        enemy2 = enemy
                if D3 > d3 and d3 <= D:
                    #현재까지의 최소 거리이면
                    D3 = d3
                    enemy3 = enemy
                elif D3 == d3 and d3 <= D:
                    if enemy3[1] > enemy[1]:
                        D3 = d3
                        enemy3 = enemy
            
            #찾은 적에 대해서 공격
            shot = set()
            if enemy1 != [0,0]:
                shot.add((enemy1[0], enemy1[1]))
                if enemy1 in cur_enemies:
                    cur_enemies.remove(enemy1)
            if enemy2 != [0,0]:
                shot.add((enemy2[0], enemy2[1]))
                if enemy2 in cur_enemies:
                    cur_enemies.remove(enemy2)
            if enemy3 != [0,0]:
                shot.add((enemy3[0], enemy3[1]))
                if enemy3 in cur_enemies:
                    cur_enemies.remove(enemy3)
            count += len(shot)
    射殺する敵についてcountはsetを用いて計算した.アーチェリーの手一人一人が同じ敵を射殺できるからだ.
    敵の移動や碁盤に敵が存在するかどうかをチェックする部分は李智で、
    import sys
    import copy
    from itertools import combinations
    
    N, M, D = map(int, input().split())
    board = []
    answer = 0
    enemies = []
    for i in range(N):
        tmp = list(map(int, input().split()))
        for j in range(M):
            if tmp[j] == 1:
                enemies.append([i,j])
        board.append(tmp)
    
    num = [i for i in range(M)]
    #가능한 궁수 배치 경우
    archers = list(combinations(num, 3))
    
    for arc1, arc2, arc3 in archers:
        cur_enemies = copy.deepcopy(enemies, key = lambda x : (-x[0], x[1]))
        count = 0
        while True:
            #1. 공격하기
            D1, D2, D3 = N+M, N+M, N+M
            enemy1, enemy2, enemy3 = [0,0], [0,0], [0,0]
            #공격할 적 찾기
            for enemy in cur_enemies:
                #현재 체크하는 적 위치~각 궁수 위치까지의 거리
                d1 = abs(N-enemy[0]) + abs(arc1-enemy[1])
                d2 = abs(N-enemy[0]) + abs(arc2-enemy[1])
                d3 = abs(N-enemy[0]) + abs(arc3-enemy[1])
    
                if D1 > d1 and d1 <= D:
                    #현재까지의 최소 거리이면
                    D1 = d1
                    enemy1 = enemy
                elif D1 == d1 and d1 <= D:
                    if enemy1[1] > enemy[1]:
                        D1 = d1
                        enemy1 = enemy
                if D2 > d2 and d2 <= D:
                    #현재까지의 최소 거리이면
                    D2 = d2
                    enemy2 = enemy
                elif D2 == d2 and d2 <= D:
                    if enemy2[1] > enemy[1]:
                        D2 = d2
                        enemy2 = enemy
                if D3 > d3 and d3 <= D:
                    #현재까지의 최소 거리이면
                    D3 = d3
                    enemy3 = enemy
                elif D3 == d3 and d3 <= D:
                    if enemy3[1] > enemy[1]:
                        D3 = d3
                        enemy3 = enemy
            
            #찾은 적에 대해서 공격
            shot = set()
            if enemy1 != [0,0]:
                shot.add((enemy1[0], enemy1[1]))
                if enemy1 in cur_enemies:
                    cur_enemies.remove(enemy1)
            if enemy2 != [0,0]:
                shot.add((enemy2[0], enemy2[1]))
                if enemy2 in cur_enemies:
                    cur_enemies.remove(enemy2)
            if enemy3 != [0,0]:
                shot.add((enemy3[0], enemy3[1]))
                if enemy3 in cur_enemies:
                    cur_enemies.remove(enemy3)
            count += len(shot)
            #2. 이동시키기
            i = 0
            while cur_enemies:
                if i >= len(cur_enemies):
                    break
                cur_enemies[i][0] += 1
                #성에 도달하면
                if cur_enemies[i][0] >= N:
                    cur_enemies.remove(cur_enemies[i])
                else:
                    i+=1
            #3. 보드에 남은 적 있는지 확인
            if not cur_enemies:
                answer = max(answer, count)
                break
    
            
    print(answer)
    コード全体を以下に示します.

    に感銘を与える



    分類はbfsなので、一番いい方法ではありませんが、ほほほ、他のメンバーの草を勉強してから解いてみましょう.
    これらの詳細な条件の実施についていろいろ考えるのは難しいですが、複数の、、、、、、、、テストケースで見つかったエラーが多いので、できるだけ紙に水道コードを書いてからコードを入力しますが、一度にすべての条件を完璧に考慮してコードに書き込むのは、まだ内功に欠けているようです^ㅠ
    論理は同じですが、ずっと間違っていて、それから出てきて、少し休んでから、また問題に答えて、問題に答えるスピードも続けば速くなります.