🌌 Мрежи, Лабиринти и Обхождане (Grids)
Мрежите (Grids) са най-честото представяне на карти в състезателното програмиране (лабиринти, игри, терени). Те са всъщност графи, където всяка клетка е връх, а съседните клетки са свързани с ребра.
1. Основни концепции
1.1. Координати и Валидност
Обикновено работим с матрица grid[R][C]. Редът е \(r\), колоната е \(c\).
Важно е винаги да проверяваме дали сме излезли извън картата.
const int MAXN = 1000;
int R, C;
int grid[MAXN][MAXN];
bool visited[MAXN][MAXN];
bool isValid(int r, int c) {
return r >= 0 && r < R && c >= 0 && c < C; // Внимавайте с 0-based vs 1-based
}
1.2. Вектори на движение (Direction Arrays)
За да не пишем 4 if-а за всяка посока, използваме масиви за промяна на координатите.
4 Посоки (Север, Юг, Запад, Изток):
8 Посоки (Включително диагонали - за King/Queen):
Ход на Коня (Knight Moves):
2. Обхождане в дълбочина (DFS) - Flood Fill
DFS е идеален за задачи от типа "намерете броя на свързаните области" (напр. острови в море) или "размер на текущата област". Алгоритъмът, известен като Flood Fill, "залива" цялата достижима зона.
Задача: Брой на островите
Дадена е карта, където 1 е земя, 0 е вода. Колко са островите?
void dfs(int r, int c) {
visited[r][c] = true;
// Опитваме и 4-те посоки
for (int i = 0; i < 4; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
// Ако е в картата, не е посетено и е земя
if (isValid(nr, nc) && !visited[nr][nc] && grid[nr][nc] == 1) {
dfs(nr, nc);
}
}
}
int countIslands() {
int islands = 0;
// Нулиране на visited...
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (grid[i][j] == 1 && !visited[i][j]) {
islands++; // Намерихме нов остров
dfs(i, j); // Маркираме цялата му територия
}
}
}
return islands;
}
3. Обхождане в ширина (BFS) - Най-кратък път
BFS е единственият правилен начин за намиране на най-кратък път в непретеглен граф (мрежа, където всяка стъпка е с цена 1). DFS не гарантира най-кратък път!
Задача: Изход от лабиринт
Минимален брой стъпки от Start (S) до End (E). # са стени.
#include <queue>
#include <tuple>
using namespace std;
int dist[MAXN][MAXN]; // Пази разстоянието. -1 за непосетено.
int bfs(int startR, int startC, int endR, int endC) {
// Инициализация
for(int i=0; i<R; i++)
for(int j=0; j<C; j++)
dist[i][j] = -1;
queue<pair<int, int>> q;
q.push({startR, startC});
dist[startR][startC] = 0;
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
if (r == endR && c == endC) return dist[r][c];
for (int i = 0; i < 4; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
// Проверка: валидност, не е стена, не е посетено
if (isValid(nr, nc) && grid[nr][nc] != '#' && dist[nr][nc] == -1) {
dist[nr][nc] = dist[r][c] + 1;
q.push({nr, nc});
}
}
}
return -1; // Няма път
}
4. Multi-Source BFS (BFS от много източници)
Ако имаме "пожар", който тръгва от 5 различни клетки едновременно, и искаме да знаем кога ще стигне до нас.
* Просто добавяме всички стартови клетки в опашката в началото (с dist = 0).
* Стартираме стандартен BFS.
5. Задачи за упражнение
- CSES Counting Rooms: Класически Connected Components.
- CSES Labyrinth: BFS + възстановяване на пътя (чрез
parentмасив). - Codeforces 598D: Igor In the Museum (Flood Fill с прекалкулация).
- UVa 439 - Knight Moves: BFS с ход на коня.
🏁 Съвети
- Винаги проверявайте границите (
isValid) първо вif-а, за да избегнетеSegmentation Faultпри достъп до масива. visistedмасивът е задължителен, за да не се въртите в кръг.- При BFS винаги използвайте
queue, а неstackили рекурсия.
6. Възстановяване на пътя (Path Reconstruction)
Често задачите изискват не само да намерите дали има път, но и да го изведете. За това пазим масив parent, който записва от къде сме дошли на всяка клетка.
struct Cell {
int r, c;
};
Cell parent[MAXN][MAXN];
int bfs_with_path(int sr, int sc, int er, int ec) {
queue<pair<int,int>> q;
q.push({sr, sc});
dist[sr][sc] = 0;
parent[sr][sc] = {-1, -1}; // Начало
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
if (r == er && c == ec) {
// Възстановяваме пътя
vector<pair<int,int>> path;
int cr = er, cc = ec;
while (cr != -1) {
path.push_back({cr, cc});
auto p = parent[cr][cc];
cr = p.r; cc = p.c;
}
reverse(path.begin(), path.end());
// Отпечатваме пътя
for (auto [x, y] : path) {
cout << "(" << x << ", " << y << ") ";
}
cout << endl;
return dist[er][ec];
}
for (int i = 0; i < 4; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
if (isValid(nr, nc) && grid[nr][nc] != '#' && dist[nr][nc] == -1) {
dist[nr][nc] = dist[r][c] + 1;
parent[nr][nc] = {r, c};
q.push({nr, nc});
}
}
}
return -1;
}
7. 0-1 BFS (Deque BFS)
Ако цената на ходовете не е еднаква, но е или 0, или 1, можем да използваме Deque BFS: * Ходове с цена 0 се добавят в началото на опашката. * Ходове с цена 1 се добавят в края на опашката.
Това запазва монотонността на разстоянията и работи за \(O(V + E)\).
deque<pair<int,int>> dq;
dq.push_back({sr, sc});
dist[sr][sc] = 0;
while (!dq.empty()) {
auto [r, c] = dq.front();
dq.pop_front();
for (int i = 0; i < 4; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
int cost = (grid[nr][nc] == 'X') ? 1 : 0; // Пример: 'X' струва 1
if (isValid(nr, nc) && dist[nr][nc] == -1) {
dist[nr][nc] = dist[r][c] + cost;
if (cost == 0) dq.push_front({nr, nc});
else dq.push_back({nr, nc});
}
}
}
8. Често срещани проблеми и оптимизации
8.1. Памет
За големи мрежи (напр. \(5000 \times 5000\)), двумерните масиви могат да са твърде големи. Използвайте:
* vector<vector<int>> за динамично заделяне.
* Едномерен масив с изчисляване на индекс: index = r * C + c.
8.2. Скорост
- При BFS използвайте
queue, а неpriority_queue(излишна сложност). - При DFS внимавайте да не превишите стековата памет при дълбока рекурсия. Ако \(R \times C > 10^6\), използвайте итеративен DFS със
stack.
🏁 Заключение
Мрежите са фундаментална тема в състезателното програмиране. Владеенето на DFS (за connected components) и BFS (за най-кратък път) ще ви отвори вратите към множество алгоритми като Dijkstra, Динамично програмиране върху графи и други.