[学習アルゴリズム]実戦アルゴリズム9講-BFS

私がバーク金督がアップロードした「実戦アルゴリズム」のビデオを見て勉強した過程を記録します.
すべての写真は巴金督のブログから持ってきたものです.
https://blog.encrypted.gg/

アルゴリズムの説明

Breadth First Search:各セルに多次元配列でアクセスする際の優先アクセス幅のアルゴリズム
BFSアルゴリズムでは座標を収容するためにキューが必要である.

開始セルをキューに入れ、アクセスタグ

を残す.

キューから要素を取り出し、そのセルの上下左右に隣接するセルに対して

を3回行う.

以前にこのバーにアクセスした場合は、何もしません.最初にこのバーにアクセスした場合は、アクセスのタグを残し、キュー

に挿入します.
を2回繰り返し、

キューが空きます.

すべてのセルが1回キューに入るため、時間的複雑度はO(N)

(N)
pairは、2つの要素を組み合わせることができるSTLであり、予めサイズ関係が設定されている.
自分で前の値を比較してから、後の値を比較します.
BFSを実装する場合は,キューに座標を配置する必要があり,pairを用いる.

インプリメンテーション

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용
int board[502][502] =
{{1,1,1,0,1,0,0,0,0,0},
 {1,0,0,0,1,0,0,0,0,0},
 {1,1,1,0,1,0,0,0,0,0},
 {1,1,0,0,1,0,0,0,0,0},
 {0,1,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0} }; // 1이 파란 칸, 0이 빨간 칸에 대응
bool vis[502][502]; // 해당 칸을 방문했는지 여부를 저장
int n = 7, m = 10; // n = 행의 수, m = 열의 수
int dx[4] = {1,0,-1,0}; // 아래쪽, 오른쪽, 윗쪽, 왼쪽 순서
int dy[4] = {0,1,0,-1}; // 상하좌우 네 방향을 의미
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  queue<pair<int,int> > Q;
  vis[0][0] = 1; // (0, 0)을 방문했다고 명시
  Q.push({0,0}); // 큐에 시작점인 (0, 0)을 삽입.
  while(!Q.empty()){
    pair<int,int> cur = Q.front(); Q.pop();
    cout << '(' << cur.X << ", " << cur.Y << ") -> ";
    for(int dir = 0; dir < 4; dir++){ // 상하좌우 칸을 살펴볼 것이다.
      int nx = cur.X + dx[dir]; // x가 행, y가 열로 생각하는게 좋다.
      int ny = cur.Y + dy[dir]; // nx, ny에 dir에서 정한 방향의 인접한 칸의 좌표가 들어감
      if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 범위 밖일 경우 넘어감, 이게 반드시 먼저 확인되어야 함 
      if(vis[nx][ny] || board[nx][ny] != 1) continue; // 이미 방문한 칸이거나 파란 칸이 아닐 경우
      vis[nx][ny] = 1; // (nx, ny)를 방문했다고 명시
      Q.push({nx,ny});
    }
  }
}

実装時の一般的なエラー

始点にアクセスしましたが、アクセスのマークは残っていません.

キューに入れたときにアクセスしたタグが残っておらず、キューから取り出したときにアクセスしたタグが残っている場合、同じセルが複数回キューに入り、タイムアウトやメモリオーバーフローを引き起こす可能性があります.

に隣接する要素が範囲を超えているかどうかのチェックにエラーが発生しました.コードにnx,nyが範囲外の場合を省略したり,変な表現をしたりする.

白峻1926号。

の上下左右に接続する画像サイズを知る->pop数

の図画紙のすべての画像を探し出す->BFSの開始点

として繰り返し文を使用できるかどうかを確認する.

白駿2178号です。

左上角から右下角までの最短経路の長さが探している問題です.

赤の格子は現在見ている格子で、黒の格子は増加した格子です.現在表示されている格子に追加されている隣接する黒い格子は、現在表示されている格子から1離れています.この性質を利用して,始点からの全距離を計算することができる.

の距離を格納するdist配列では,上下左右の格子を見たときに値を置けばよい.この配列を-1にリセットしておけば、vis配列を別途設定することなくアクセスを確認できます.

白駿7576号です。

これは複数の開始点を囲むBFSの問題である.すべての始点をキューに入れ、BFSを迂回すればよい.

BFSを迂回する場合、キュー内のスタック順序は距離順でなければなりません.

白駿4179号です。

問題は

智勲に対するBFSと対火のBFSを全部回せばいいということです.

の起点は2つの問題で、智勲は火の影響を受けているが、火は智勲の影響を受けていないので、まず不満を伝え続けることは可能だ.しかし,AとBの2つの始点が存在し,互いに影響し合うと,どちらを最後まで伝播するかは不可能である.したがって,互いに独立せず,互いに影響を及ぼさなければ,まず1つを処理し,残りの方法を処理することは不可能である.