[BOJ] - 16924

12264 ワード
brute force 再オープン テキストリンク
https://www.acmicpc.net/problem/16924

フルナビゲーション


  • 可能な限り数を探索するタイプです.

  • 再帰形式で問題を解く場合が多く,一歩ごとに次の再帰を実現し,不可能をスキップする場合がある.

  • 復帰の終点(脱出条件)に達した場合、1を返し、状況の数を計算します

  • 数の場合の問題は完全に探求型である

  • ブルートフォースは完全な探索アルゴリズムである.
  • 線形構造
    • を順次ナビゲートする.
  • 비선형구조는 DFS 또는 BFS 를 이용한다

  • つまり、ドアを回って条件を一つ一つチェックすることで、

  • DFS、BFS等による問題解決

    • ノート


    に答える


    これは交差できる問題で、可能な答えを印刷すればいい問題です.
    1)NxM全体に移動し、最大の配置が可能な十字架を配置します.
    2)最終状態確認で解除

    に質問


    可能な場合は、十字架を解放することで数をナビゲートできます.失敗した場合は、他の状況の数を復元しようとします.
    これは問題だと思った.
  • はすべての場合の数字を試み、できればいずれかを出力することができ、最大サイズだけを試してみるべきだ.
    • 耳で
  • を解きたいなら、下のように解くことができます.
    1)完全探索の際に落下しない
    2)*の場合、最大サイズの十字架をテストしてください.
    3)回帰開始部分でテストが成功したかどうか
    4)トップに戻ると、
    • これは交差できる問題で、可能な答えを印刷すればいい問題です.
    N x M全体に移動し、最大サイズの十字架を配置します.
    最終状態を確認するように解く.

    コード#コード#

    import sys

sys.stdin = open('16924.txt')

n, m = list(map(int,input().split()))

data = ['' for _ in range(n)]
for i in range(n):
    line = input()
    data[i] = line

check = [[False for _ in range(m)] for _ in range(n)]

# for 문 사용해서 완전탐색
# 채울 수 있는 모든 곳을 최대 크기의 십자가로 채운다
ans = set()
for i in range(n):
    for j in range(m):

        if data[i][j] == '.':
             continue

        max_size = 0
        dl = 1
        while True:

            if i - dl < 0 or i + dl >= n or j - dl < 0 or j + dl >= m:
                break

            if data[i-dl][j] == '.' or data[i+dl][j] == '.' or data[i][j-dl] == '.' or data[i][j+dl] == '.':
                break

            max_size = dl
            dl += 1

        if max_size != 0:
            check[i][j] = True
            for k in range(1, max_size + 1):
                check[i+k][j] = True
                check[i-k][j] = True
                check[i][j+k] = True
                check[i][j-k] = True

            ans.add((i+1, j+1, max_size))


# 문제 요구사항 만족 여부 체크
for i in range(n):
    for j in range(m):
        if data[i][j] == '*' and not check[i][j]:
            print(-1)
            exit()

print(len(ans))
for d in ans:
    print(' '.join(list(map(str,d))))
    泡立つような、カラフルなサイトのボタンのトリオ
    Docker Swarmチュートリアルやってみた(overlayネットワーク)