DFS、BFS-例

14766 ワード
イコテ BFS アルゴリズム#アルゴリズム# DFS テキストリンク

例）冷凍飲料


イコール149 p

質問する


  • 制限
  • 1秒/128 MB

  • 入力
  • 氷棚縦長N,M(1<=N,M<=1000)
  • 2列からN+1列までの氷棚形状(0=穴、1=非)

  • しゅつりょく
  • 一度に作れるアイスクリームの数出力

  • 例
    N*Mサイズの氷棚があります.
    穿孔した部分は0で、仕切りのある部分は.
    00110
    00011
    11111
    00000
    もしそうであれば、アイスクリームを3つ生成します.

    • ソリューションの探し方

  • 行列の形態をグラフ思考に変換する.
  • pytonicの上下左右移動法に熟知し、
  • 接続ブロックの検索=DFS/BFS接続のすべての部分にのみナビゲート

  • 個人的にはDFS/BFS=の「ナビ」を探すだけです.
    探索できる条件は「グラフィック(ブロック)」の中で「接続された経路しか探索できない」ことが発見されてから,なぜDFS/BFSを書くのかが分かる.

  • 「どのようにしてブロックを見つけることができますか?」->ブロック=1つのグラフィック"の場合、DFS/BFSによってすべての接続ノードを参照してブロックを区別することができる.
    考えの行方は望ましいようだ.

    • 解決策

  • 特定の場所の周辺上、下、左、右を表示した後、周辺場所に0の値があるがアクセスされていない場所がある場合は、その場所にアクセスします.
  • でアクセスした場所で、上、下、左、右を確認してアクセスを再開すると、接続されているすべての場所にアクセスできます.
  • 1-2プロセスをすべてのノードに繰り返し、アクセスされていないポイントの数を計算します.

    • コード#コード#

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

graph = []
for i in range (n) :
  graph.append(list(map(int, input())))

# DFS
def DFS(x, y) :
  stack = []
  # 주어진 범위를 벗어나는 경우 즉시 종료
  if x <= -1 or x >= n or y <= -1 or y >= m :
    return False
  # 현재 노드를 아직 방문하지 않았다면
  if graph[x][y] == 0 :
    # 해당 노드 방문 처리
    # 상 하 좌 우 위치도 모두 재귀적으로 호출
    dfs(x-1, y)
    dfs(x, y-1)
    dfs(x+1, y)
    dfs(x, y+1)
    return True
  return False

# 모든 노드에 대하여 음료수 채우기
result = 0
for i in range(n) :
  for j in range(m) :
    # 현재 위치에서 DFS 수행
    if DFS(i, j) == True :
      result += 1

print(result)

    覚えてほしい。

  • チェス盤を移動する方法
  • 既存のDFS(使用リスト)は、すべての接続ノードを再帰的に呼び出し、
    • .
  • 2*2テーブルを基準に、既存のdfsを少し変更して、dfs()を4方向に統一的に呼び出す.
  • はほとんど定式的な使い方ですから、よく知っていますね.

    • 迷宮からの脱出


    イコテ152 p

    質問する

  • 制限
  • 時間1秒/メモリ128 MB
    • 入力
  • 整数N,M(4<=N,M<=200)
  • N行0または1のM整数、迷路情報
    • を提供する
  • 出力
  • 最小移動格子数出力
  • 状況
  • N*M迷宮に閉じ込められている.
    (1,1)から、出口(N,M)を歩きます.
  • 0を避けて1にしか移動できません.
  • を脱出するために移動しなければならない最小格子数
    • を求める.

    (プール)BFSを適用する理由

  • から始まり、近いノードから順に全ノードをブラウズします.
    =[近接](Near)ノードからナビゲートを開始し、初めて条件を満たすときに[最小](Minimum)であることを保証します.
    • 上のDFSと同じように、
    BFSは探索アルゴリズムであるが,なぜこれに応用されるのか.
    BFSの特徴から(金利実現自体)
    BFSが最初に条件を満たしたとき、「最小」であることを推定してほしい.
    壁が0,可走路が1の場合,BFSが実行されるたびに++が加算され,最終目的地はこれまでの移動数が記録される.

    次のコードを見て、カウントダウン方法を見てみましょう.
  • のようにカウントダウンし、<0は壁が歩けないこと、2面がすでにアクセスできないこと>で、プロンプト上の点にアクセスするかどうかを決めることができます.

    • それ以外は

  • の2 Dリストのグラフィックの描画方法
    dx,dy(移動可能な座標)による
  • 4号室の実現方法

    コード#コード#

    from collections import deque

# N, M 공백으로 구분하여 입력받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력받기
graph = []
for i in range (n) :
  graph.append(list(map(int, input())))

# 이동할 네 방향 정의
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# BFS 코드 구현 
def bfs(x,y) :

  # queue 구현을 위해 deque라이브러리 사용
  queue = deque()
  queue.append((x,y))
 
  # queue가 빌때까지 반복
  while queue : 
    x, y = queue.popleft()
    # 현재 위치에서 네 방향으로의 위치 확인
    for i in range(4) :
      # nx,ny = 갈수도 있는 좌표
      nx = x + dx[i] 
      ny = y + dy[i]
      # 미로 찾기 공간을 벗어난 경우 무시
      if nx<0 or ny<0 or nx>=n or ny>=m :
        continue
      # 벽인 경우 무시
      if graph[nx][ny] == 0 :
        continue
      # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
      ####################################
      # 0이면 벽이어서 못가고, 2면 이미 방문해서 못간다.
      if graph[nx][ny] == 1 :
      ##########################
        graph[nx][ny] = graph[x][y] + 1 #1을 더해서, 지금까지 온 만큼을 카운트 한다!!
      #########################
        queue.append((nx, ny)) # nx, ny가 진짜 가는 좌표가 된다.
   # 가장 오른쪽 아래까지의 최단거리 반환
   return graph[n-1][m-1]
    • Vue 3でアクセス可能なトグルスイッチを構築する方法
    react学習dad 3(構成部品)