Introduction à la résolution par BFS

La recherche en largeur (BFS) est une technique efficace pour déterminer le chemin le plus court dans un environnement structuré en grille, où chaque déplacement a un coût uniforme. Cet article explique comment appliquer BFS pour naviguer sur une carte carrée, en évitant les obstacles, afin de trouver la distance minimale entre deux points.

Implémentation générale de BFS sur une grille

Considérons une grille de taille n×n. L'algorithme BFS commence à un point de départ et explore systématiquement tous les voisins accessibles, en enregistrant les distances. Ci-dessous, une implémentation en C++ qui calcule les distances à partir d'un point source vers tous les autres points de la grille.

#include <iostream>
#include <queue>
using namespace std;

const int MAX_DIM = 1010;
int taille;
int debutX, debutY;
int dist[MAX_DIM][MAX_DIM];
bool visite[MAX_DIM][MAX_DIM];
int deltaX[4] = {0, 0, -1, 1};
int deltaY[4] = {-1, 1, 0, 0};

void bfs() {
    queue<pair<int, int>> file;
    visite[debutX][debutY] = true;
    dist[debutX][debutY] = 0;
    file.push({debutX, debutY});
    
    while (!file.empty()) {
        auto courant = file.front();
        file.pop();
        int posX = courant.first, posY = courant.second;
        
        for (int i = 0; i < 4; i++) {
            int nouvX = posX + deltaX[i];
            int nouvY = posY + deltaY[i];
            
            if (nouvX >= 1 && nouvX <= taille && nouvY >= 1 && nouvY <= taille && !visite[nouvX][nouvY]) {
                visite[nouvX][nouvY] = true;
                dist[nouvX][nouvY] = dist[posX][posY] + 1;
                file.push({nouvX, nouvY});
            }
        }
    }
}

int main() {
    cin >> taille >> debutX >> debutY;
    bfs();
    for (int i = 1; i <= taille; i++) {
        for (int j = 1; j <= taille; j++) {
            cout << dist[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

Cette version utilise des noms de variables différents et une structure de condition légèrement modifiée pour vérifier les limites. L'algorithme reste identique : exploration en largeur des cellules adjacentes.

Problème spécifique : Quitter Zhongshan Road (Luogu P1746)

Le problème demande de trouver la distance la plus courte entre deux points sur une carte n×n (n≤1000), où les cellules sont marquées comme '0' pour les routes passables ou '1' pour les magasins bloquants. Les déplacements ne sont autorisés que verticalement ou horizontalement.

Format d'entrée

• Première ligne : un entier n.
• Lignes suivantes : n lignes représentant la carte, chaque ligne est une chaîne de caractères de longueur n avec '0' et '1'.
• Dernière ligne : quatre entiers x1, y1, x2, y2 pour les coordonnées de départ et d'arrivée.

Format de sortie

Un seul entier : la distance minimale, ou -1 si aucun chemin n'existe.

Solution BFS adaptée avec obstacles

Pour ce problème, BFS est appliqué en vérifiant les obstacles. L'algorithme s'arrête dès que la destination est atteinte pour optimiser le temps. Voici une implémentation restructurée.

#include <iostream>
#include <queue>
using namespace std;

const int LIMITE = 1010;
int dimension;
char carte[LIMITE][LIMITE];
int distance[LIMITE][LIMITE];
bool marque[LIMITE][LIMITE];
int dirX[4] = {1, -1, 0, 0};
int dirY[4] = {0, 0, 1, -1};
int startX, startY, endX, endY;

void parcoursLargeur() {
    queue<pair<int, int>> attente;
    marque[startX][startY] = true;
    distance[startX][startY] = 0;
    attente.push({startX, startY});
    
    while (!attente.empty()) {
        auto noeud = attente.front();
        attente.pop();
        int x = noeud.first, y = noeud.second;
        
        for (int k = 0; k < 4; k++) {
            int nx = x + dirX[k];
            int ny = y + dirY[k];
            
            if (nx >= 1 && nx <= dimension && ny >= 1 && ny <= dimension && carte[nx][ny] == '0' && !marque[nx][ny]) {
                marque[nx][ny] = true;
                distance[nx][ny] = distance[x][y] + 1;
                if (nx == endX && ny == endY) {
                    return;
                }
                attente.push({nx, ny});
            }
        }
    }
}

int main() {
    cin >> dimension;
    for (int i = 1; i <= dimension; i++) {
        for (int j = 1; j <= dimension; j++) {
            cin >> carte[i][j];
        }
    }
    cin >> startX >> startY >> endX >> endY;
    parcoursLargeur();
    if (marque[endX][endY]) {
        cout << distance[endX][endY] << endl;
    } else {
        cout << -1 << endl;
    }
    return 0;
}

Cette version modifie les noms des tableaux et variables, et ajoute une vérification explicite pour le cas où aucune route n'est disponible. La logique de BFS est préservée, mais la structure du code est réorganisée pour plus de clarté.