Поиск в ширину: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показаны 2 промежуточные версии этого же участника)
Строка 1: Строка 1:
== TLDR ==
<youtube width="300" height="180">4iDv8Zu8L3I</youtube>
<youtube width="300" height="180">jqtCPow_iGY</youtube>
<youtube width="300" height="180">xGvIoExlqIw</youtube>
== Стандартный BFS ==
== Стандартный BFS ==
  vector<int> bfs(vector<vector<int>> &graph, int start) {
  vector<int> bfs(vector<vector<int>> &graph, int start) {
Строка 41: Строка 46:
             int tx = x + dx[d];
             int tx = x + dx[d];
              
              
             if (0 <= ty && ty < a.size() && 0 <= tx && tx < a[0].size() && a[y][x] && dist[ty][tx] == 1e9) {
             if (0 <= ty && ty < a.size() && 0 <= tx && tx < a[0].size() && a[ty][tx] && dist[ty][tx] > dist[y][x] + 1) {
                 dist[ty][tx] = dist[y][x] + 1;
                 dist[ty][tx] = dist[y][x] + 1;
                 q.push({ ty, tx });
                 q.push({ ty, tx });

Текущая версия от 15:25, 24 мая 2023

TLDR

Стандартный BFS

vector<int> bfs(vector<vector<int>> &graph, int start) {
    vector<int> dist(graph.size(), 1e9);
    queue<int> q;

    dist[start] = 0;
    q.push(start);

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        for (int to : graph[v]) {
            if (dist[to] > dist[v] + 1) {
                dist[to] = dist[v] + 1;
                q.push(to);
            }
        }
    }

    return dist;
}

BFS на неявном графе

vector<vector<int>> bfs(vector<vector<int>> &a, int startY, int startX) {
    vector<vector<int>> dist(a.size(), vector<int>(a[0].size(), 1e9));
    queue<pair<int, int>> q;
    
    dist[startY][startX] = 0;
    q.push({ startY, startX });
    
    vector<int> dy = { -1, 0, 1, 0 };
    vector<int> dx = { 0, 1, 0, -1 };
    
    while (!q.empty()) {
        auto [y, x] = q.front();
        q.pop();
            
        for (int d = 0; d < dy.size(); d++) {
            int ty = y + dy[d];
            int tx = x + dx[d];
            
            if (0 <= ty && ty < a.size() && 0 <= tx && tx < a[0].size() && a[ty][tx] && dist[ty][tx] > dist[y][x] + 1) {
                dist[ty][tx] = dist[y][x] + 1;
                q.push({ ty, tx });
            }
        }
    }
    
    return dist;
}

Ссылки на задачи

Ссылки