SyntaxPilot
Courses/Competitive Programming/Lesson 45
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 45 of 90

Graphs for contests: BFS/DFS templates, grids, 0-1 BFS

queued

These are the notes for Competitive Programming episode 45, the first episode of the graphs section. Three original problems build the three templates every contestant types from memory. Road Groups stores a graph as an adjacency list and counts connected components with DFS. Courier Grid treats a grid as a graph with dx/dy arrays; the obvious DFS gives 7 where the answer is 3 (Wrong Answer), and spreading out like ripples in a pond with a queue gives BFS, which is accepted in O(n·m). On a 1000 × 1000 grid a recursive flood fill crashes with a stack overflow (Segmentation fault), fixed with an explicit stack. Wall Breaker makes some steps cost 1 and others 0: plain BFS prints 1 where the answer is 0, and a deque (free steps to the front, paid steps to the back) gives 0-1 BFS, checked against Dijkstra in a stress test. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook

A delivery rider works in an old city where the streets form a grid. Some blocks are buildings, the rest are lanes. She wants the fewest steps from the shop (S) to the customer (T). Ask anyone how they would find it and they describe BFS without knowing the name: "first check every lane one step away, then every lane two steps away, …". That is exactly what happens when you drop a stone in a pond: the rings spread out evenly, near water first, far water later, and the first ring to touch a floating leaf took the shortest way there.

Later the rider gets a demolition crew: walking along a lane is free, breaking through a building costs 1. Now "nearest" means "cheapest", not "fewest steps", and the ripples need a small upgrade: free steps are handled before everything else at the same cost.

Problem A · Road Groups

(Written for this course, in the style of an AtCoder Beginner Contest problem.)

A district has n villages numbered 1 … n and m two-way roads; road i joins villages a_i and b_i. A group is a set of villages that can all reach each other by road. Print the number of groups.

  • Input: n and m (1 ≤ n ≤ 2 · 10^5, 0 ≤ m ≤ 2 · 10^5), then m lines a_i b_i.
  • Output: the number of groups.
Input Output
6 3 / 1 2 / 2 3 / 4 5 3 ({1, 2, 3}, {4, 5}, {6})
4 0 4 (no roads: every village alone)

In graph words: villages are nodes (vertices), roads are edges, and a group is a connected component.

Storing the graph: the adjacency list

For each node keep the list of its neighbours: vector<vector<int>> adj(n + 1). A two-way road is added twice, adj[a].push_back(b) and adj[b].push_back(a). Memory is O(n + m). An adjacency matrix (an n × n table of 0/1) would need 4 · 10^10 cells for n = 2 · 10^5, so contests almost always use lists.

DFS: go deep, mark seen

Depth-first search starts at a node, marks it seen, and recursively visits every neighbour that is not seen yet. Every node and every edge is looked at a constant number of times: O(n + m). Each DFS started from an unseen node discovers exactly one new group, so counting the starts counts the groups.

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> adj;
vector<bool> seen;

void dfs(int u) {
    seen[u] = true;
    for (int v : adj[u])
        if (!seen[v]) dfs(v);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    adj.assign(n + 1, {});
    seen.assign(n + 1, false);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);              // a road works both ways
        adj[b].push_back(a);
    }
    int groups = 0;
    for (int u = 1; u <= n; u++)
        if (!seen[u]) { groups++; dfs(u); }
    cout << groups << "\n";
}
3
4

Problem G1 · Courier Grid

(Written for this course, in the style of a Codeforces Div. 3 problem.)

The city is an n × m grid of characters: . is a lane, # is a building, S is the start and T the target (both are lanes). Each step moves to the cell above, below, left or right; buildings and the outside of the grid cannot be entered. Print the fewest steps from S to T, or −1 if T cannot be reached.

  • Input: n and m (1 ≤ n, m ≤ 1000), then n strings of length m. Exactly one S and one T.
  • Output: the fewest steps, or −1.
Input Output
3 4 / S..T / .##. / .... 3
2 3 / S#T / .#. -1 (the buildings wall T off)
1 2 / ST 1

A grid is a graph you never build

Every cell (x, y) is a node, and a step to a side neighbour is an edge. The contest trick is two direction arrays:

int dx[4] = {1, 0, -1, 0};   // down, right, up, left
int dy[4] = {0, 1, 0, -1};
// the four neighbours of (x, y): (x + dx[d], y + dy[d]) for d = 0..3

Always do the bounds check 0 <= nx < n && 0 <= ny < m before reading g[nx][ny]: a cell outside the grid does not exist, and reading it is undefined behaviour. For 8 directions (king moves) or knight moves, only the arrays change.

The obvious attempt: DFS with dist = parent + 1 (Wrong Answer)

We already have DFS, so give each newly reached cell the distance of its parent plus one:

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {1, 0, -1, 0};                 // down, right, up, left
int dy[4] = {0, 1, 0, -1};
int n, m;
vector<string> g;
vector<vector<int>> dist;

void dfs(int x, int y) {
    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d], ny = y + dy[d];
        if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;   // off the grid
        if (g[nx][ny] == '#' || dist[nx][ny] != -1) continue;
        dist[nx][ny] = dist[x][y] + 1;
        dfs(nx, ny);
    }
}

int main() {
    cin >> n >> m;
    g.resize(n);
    for (auto &row : g) cin >> row;
    dist.assign(n, vector<int>(m, -1));
    int sx = 0, sy = 0, tx = 0, ty = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 'S') sx = i, sy = j;
            if (g[i][j] == 'T') tx = i, ty = j;
        }
    dist[sx][sy] = 0;
    dfs(sx, sy);
    cout << dist[tx][ty] << "\n";
}
7

The answer is 3, not 7. With the direction order down, right, up, left, DFS dives down the left column, runs along the bottom row and climbs up the right side, reaching T after 7 steps. T is then marked, and the short path along the top row is never used to improve it. DFS finds a path, not the shortest one. (A DFS that tries every simple path and keeps the best is correct but exponential.)

BFS: layer by layer with a queue

To get shortest paths we must reach cells in order of distance: everything at distance 1, then everything at distance 2, and so on, like the rings in the pond. A queue (first in, first out) does exactly that: cells at distance d are all taken out before any cell at distance d + 1, because the d + 1 cells were pushed later. The first time a cell is reached, it is reached by a shortest path, so its distance is final.

Step Taken out New cells (distance) Queue after
0 — S (0) S
1 S (1,0) (1), (0,1) (1) (1,0) (0,1)
2 (1,0), (0,1) (2,0) (2), (0,2) (2) (2,0) (0,2)
3 (2,0), (0,2) (2,1) (3), T = (0,3) (3) …

dist doubles as the "seen" array: −1 means not reached yet, and if T is never reached the answer is −1 automatically.

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {1, 0, -1, 0};                 // down, right, up, left
int dy[4] = {0, 1, 0, -1};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for (auto &row : g) cin >> row;
    int sx = 0, sy = 0, tx = 0, ty = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 'S') sx = i, sy = j;
            if (g[i][j] == 'T') tx = i, ty = j;
        }
    vector<vector<int>> dist(n, vector<int>(m, -1));
    queue<pair<int, int>> q;
    dist[sx][sy] = 0;
    q.push({sx, sy});
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (g[nx][ny] == '#' || dist[nx][ny] != -1) continue;
            dist[nx][ny] = dist[x][y] + 1;    // one layer further out
            q.push({nx, ny});
        }
    }
    cout << dist[tx][ty] << "\n";
}
3
-1
1

The worst case, a 1000 × 1000 grid with 20% buildings built inside the program, S in the top-left and T in the bottom-right corner:

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {1, 0, -1, 0};                 // down, right, up, left
int dy[4] = {0, 1, 0, -1};

int main() {
    int n = 1000, m = 1000;                  // worst case, built here
    vector<string> g(n, string(m, '.'));
    mt19937 rng(45);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (rng() % 10 < 2) g[i][j] = '#';   // 20% buildings
    int sx = 0, sy = 0, tx = n - 1, ty = m - 1;
    g[sx][sy] = 'S';
    g[tx][ty] = 'T';
    vector<vector<int>> dist(n, vector<int>(m, -1));
    queue<pair<int, int>> q;
    dist[sx][sy] = 0;
    q.push({sx, sy});
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (g[nx][ny] == '#' || dist[nx][ny] != -1) continue;
            dist[nx][ny] = dist[x][y] + 1;    // one layer further out
            q.push({nx, ny});
        }
    }
    cout << dist[tx][ty] << "\n";
}
1998

1998 = (1000 − 1) + (1000 − 1), the corner-to-corner distance, in a few milliseconds. Each cell enters the queue at most once and looks at 4 neighbours: O(n·m).

Recursion has a depth limit: stack overflow on 10^6 cells

Every recursive call keeps a stack frame (its local variables and return address) on the call stack until it returns. The stack is small: 8 MB by default on Linux (the SyntaxPilot compiler runs with 8 MB), and judges differ (Codeforces gives a large stack, many others do not). On an empty 1000 × 1000 field, a recursive flood fill can be 10^6 calls deep before the first one returns:

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {1, 0, -1, 0};                 // down, right, up, left
int dy[4] = {0, 1, 0, -1};
int n = 1000, m = 1000;
vector<string> g(n, string(m, '.'));

void dfs(int x, int y) {
    g[x][y] = '#';                          // mark: visited
    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d], ny = y + dy[d];
        if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
        if (g[nx][ny] == '.') dfs(nx, ny);
    }
}

int main() {
    int parts = 0;                           // 1000 x 1000 empty field
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == '.') { parts++; dfs(i, j); }
    cout << parts << "\n";
}
Segmentation fault   ← verdict: Runtime Error (SIGSEGV)

The logic is right; the stack ran out. The fix is to keep our own stack in a vector, which lives on the heap where there is plenty of room. Mark a cell when it is pushed, so it is pushed only once:

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {1, 0, -1, 0};                 // down, right, up, left
int dy[4] = {0, 1, 0, -1};
int n = 1000, m = 1000;
vector<string> g(n, string(m, '.'));

void fill(int sx, int sy) {
    vector<pair<int, int>> st = {{sx, sy}};   // our own stack, on the heap
    g[sx][sy] = '#';
    while (!st.empty()) {
        auto [x, y] = st.back();
        st.pop_back();
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (g[nx][ny] == '.') { g[nx][ny] = '#'; st.push_back({nx, ny}); }
        }
    }
}

int main() {
    int parts = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == '.') { parts++; fill(i, j); }
    cout << parts << "\n";
}
1

Rule of thumb: recursion depth up to about 10^4–10^5 is usually fine; for 10^6 (big grids, long paths, a "bamboo" tree) use BFS or an explicit stack.

Problem G2 · Wall Breaker

(Written for this course.)

Same grid, but the rider now has a demolition crew. Stepping onto a building breaks it and costs 1; stepping onto a lane (. or T) costs 0. Moving outside the grid is not allowed. Print the minimum number of buildings that must be broken to get from S to T. (T is always reachable now.)

Input Output
3 3 / S#T / .#. / ... 0 (walk around the bottom)
3 3 / S#T / ##. / #.. 1
1 2 / ST 0

The obvious attempt: plain BFS counting walls (Wrong Answer)

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {1, 0, -1, 0};                 // down, right, up, left
int dy[4] = {0, 1, 0, -1};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for (auto &row : g) cin >> row;
    int sx = 0, sy = 0, tx = 0, ty = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 'S') sx = i, sy = j;
            if (g[i][j] == 'T') tx = i, ty = j;
        }
    vector<vector<int>> walls(n, vector<int>(m, -1));
    queue<pair<int, int>> q;
    walls[sx][sy] = 0;
    q.push({sx, sy});
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m || walls[nx][ny] != -1) continue;
            walls[nx][ny] = walls[x][y] + (g[nx][ny] == '#');   // first visit wins
            q.push({nx, ny});
        }
    }
    cout << walls[tx][ty] << "\n";
}
1
1

The first sample should print 0. BFS reaches T first through the wall (2 steps, 1 wall) and never revisits it; the free road around the bottom takes 6 steps. BFS orders cells by the number of steps, but we are paying for walls.

0-1 BFS: a deque, 0 to the front, 1 to the back

We need cells in order of cost. Dijkstra's algorithm (next episode) does that with a priority queue in O(E log V). When every edge weight is 0 or 1 there is a simpler, linear trick. Keep a deque (double-ended queue: push and pop at both ends). At any moment it holds cells of only two costs: d at the front and d + 1 at the back. Taking a free step keeps cost d, so the new cell goes to the front; breaking a wall gives d + 1, so it goes to the back. The deque stays sorted by cost, so we always take a cheapest cell, exactly like Dijkstra, with no logarithm.

Unlike plain BFS a cell can be improved after it was first reached (in sample 1, T is first reached with cost 1 through the wall, then improved to 0), so we compare dist[x][y] + w < dist[nx][ny] instead of checking "seen". This comparison step is called relaxation.

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {1, 0, -1, 0};                 // down, right, up, left
int dy[4] = {0, 1, 0, -1};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for (auto &row : g) cin >> row;
    int sx = 0, sy = 0, tx = 0, ty = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 'S') sx = i, sy = j;
            if (g[i][j] == 'T') tx = i, ty = j;
        }
    const int INF = 1e9;
    vector<vector<int>> dist(n, vector<int>(m, INF));
    deque<pair<int, int>> dq;
    dist[sx][sy] = 0;
    dq.push_back({sx, sy});
    while (!dq.empty()) {
        auto [x, y] = dq.front();
        dq.pop_front();
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            int w = (g[nx][ny] == '#');           // a wall costs 1, a road 0
            if (dist[x][y] + w < dist[nx][ny]) {
                dist[nx][ny] = dist[x][y] + w;
                if (w == 0) dq.push_front({nx, ny});
                else dq.push_back({nx, ny});
            }
        }
    }
    cout << dist[tx][ty] << "\n";
}
0
1
0

The worst case: 10^6 cells, half of them walls:

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {1, 0, -1, 0};                 // down, right, up, left
int dy[4] = {0, 1, 0, -1};

int main() {
    int n = 1000, m = 1000;                  // worst case, built here
    vector<string> g(n, string(m, '.'));
    mt19937 rng(45);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (rng() % 10 < 5) g[i][j] = '#';   // 50% walls
    int sx = 0, sy = 0, tx = n - 1, ty = m - 1;
    g[sx][sy] = 'S';
    g[tx][ty] = 'T';
    const int INF = 1e9;
    vector<vector<int>> dist(n, vector<int>(m, INF));
    deque<pair<int, int>> dq;
    dist[sx][sy] = 0;
    dq.push_back({sx, sy});
    while (!dq.empty()) {
        auto [x, y] = dq.front();
        dq.pop_front();
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            int w = (g[nx][ny] == '#');           // a wall costs 1, a road 0
            if (dist[x][y] + w < dist[nx][ny]) {
                dist[nx][ny] = dist[x][y] + w;
                if (w == 0) dq.push_front({nx, ny});
                else dq.push_back({nx, ny});
            }
        }
    }
    cout << dist[tx][ty] << "\n";
}
128

A stress test against Dijkstra

1000 random grids of size up to 8 × 8, each cell a wall with probability 1/2, from the top-left to the bottom-right corner, 0-1 BFS against Dijkstra with a priority queue:

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {1, 0, -1, 0};                 // down, right, up, left
int dy[4] = {0, 1, 0, -1};
int n, m;
vector<string> g;

int zeroOne() {
    vector<vector<int>> dist(n, vector<int>(m, 1e9));
    deque<pair<int, int>> dq;
    dist[0][0] = 0;
    dq.push_back({0, 0});
    while (!dq.empty()) {
        auto [x, y] = dq.front();
        dq.pop_front();
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            int w = (g[nx][ny] == '#');
            if (dist[x][y] + w < dist[nx][ny]) {
                dist[nx][ny] = dist[x][y] + w;
                if (w == 0) dq.push_front({nx, ny}); else dq.push_back({nx, ny});
            }
        }
    }
    return dist[n - 1][m - 1];
}
int dijkstra() {
    vector<vector<int>> dist(n, vector<int>(m, 1e9));
    priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> pq;
    dist[0][0] = 0;
    pq.push({0, 0, 0});
    while (!pq.empty()) {
        auto [dd, x, y] = pq.top();
        pq.pop();
        if (dd > dist[x][y]) continue;
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            int nd = dd + (g[nx][ny] == '#');
            if (nd < dist[nx][ny]) { dist[nx][ny] = nd; pq.push({nd, nx, ny}); }
        }
    }
    return dist[n - 1][m - 1];
}
int main() {
    mt19937 rng(45);
    for (int t = 1; t <= 1000; t++) {
        n = rng() % 8 + 1;
        m = rng() % 8 + 1;
        g.assign(n, string(m, '.'));
        for (auto &row : g) for (char &c : row) if (rng() % 2) c = '#';
        if (zeroOne() != dijkstra()) { cout << "mismatch on test " << t; return 0; }
    }
    cout << "all 1000 tests passed";
}
all 1000 tests passed

Complexity vs the constraints

V = n·m ≤ 10^6 cells, E ≈ 4V moves.

Method Time Memory n = m = 1000
DFS for shortest path O(V + E) O(V) wrong answer (not shortest)
DFS over all simple paths exponential O(V) hopeless
BFS O(V + E) ≈ 5 · 10^6 O(V) accepted, milliseconds
recursive DFS / flood fill O(V + E) O(V) stack crashes: depth 10^6 > 8 MB stack
explicit-stack DFS O(V + E) O(V) heap accepted
0-1 BFS (weights 0/1) O(V + E) O(V) accepted, milliseconds
Dijkstra (weights 0/1) O(E log V) ≈ 10^8 O(V + E) accepted, slower

Memory: one vector<vector<int>> of 10^6 ints is 4 MB, plus about 24 bytes of overhead per row.

Common mistakes (and the real outputs)

Mistake What you see Why Fix
DFS with dist = parent + 1 for shortest paths 7 (expected 3): Wrong Answer DFS finds a path, not the shortest BFS with a queue
recursive DFS on 10^6 cells Segmentation fault → Runtime Error (SIGSEGV) the call stack (8 MB) overflows BFS or an explicit vector stack
plain BFS when steps cost 0 or 1 1 (expected 0): Wrong Answer BFS orders by steps, not by cost 0-1 BFS with a deque
reading g[nx][ny] before the bounds check undefined behaviour (garbage or a crash) the cell is outside the grid check 0 <= nx < n && 0 <= ny < m first
marking a cell seen when it is popped, not pushed (BFS) TLE / MLE the same cell is pushed many times mark when pushing
one-way adj[a].push_back(b) for a two-way road wrong groups b cannot reach a push both directions
dist filled with 0 instead of −1 unreachable T prints 0 0 is a real distance use −1 (or INF) for "not reached"

Mini project

Build a grid toolkit you can paste into contests: a function bfs(g, sources) that returns the distance table from one or many start cells, a function components(g, ch) that labels every group of character ch with an explicit stack, and a function zeroOne(g, cost) where cost(from, to) returns 0 or 1. Test it with a random grid generator and a slow checker (Dijkstra) like the stress test above, and time each function on a 1000 × 1000 grid. Then add a path() helper that rebuilds the route from a parent table and prints it as a string of D, R, U, L.

Practice

These are the four homework problems from the episode. Every answer below came from a compiled C++ program (g++ -O2 -std=c++17).

1. Count the islands. An n × m grid of . (water) and # (land). An island is a group of # cells joined through side neighbours. Print the number of islands.

Solution

Scan every cell; each # that is not yet seen starts a new island, which is flooded with BFS (a queue, so no recursion depth problem). O(n·m).

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for (auto &row : g) cin >> row;
    int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
    vector<vector<bool>> seen(n, vector<bool>(m, false));
    int islands = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            if (g[i][j] != '#' || seen[i][j]) continue;
            islands++;                          // a new island: flood it with BFS
            queue<pair<int, int>> q;
            q.push({i, j});
            seen[i][j] = true;
            while (!q.empty()) {
                auto [x, y] = q.front();
                q.pop();
                for (int d = 0; d < 4; d++) {
                    int nx = x + dx[d], ny = y + dy[d];
                    if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                    if (g[nx][ny] == '#' && !seen[nx][ny]) { seen[nx][ny] = true; q.push({nx, ny}); }
                }
            }
        }
    cout << islands << "\n";
}

Input 4 5 / #..## / #...# / ..#.. / ##..#:

5

2. Knight moves. On an n × n chessboard (n ≤ 1000), print the fewest knight jumps from square (r1, c1) to (r2, c2), or −1 if impossible.

Solution

BFS where the 8 knight jumps are the edges: dx = {1, 2, 2, 1, −1, −2, −2, −1}, dy = {2, 1, −1, −2, −2, −1, 1, 2}. O(n²).

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, r1, c1, r2, c2;
    cin >> n >> r1 >> c1 >> r2 >> c2;           // board n x n, squares 1..n
    int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1}, dy[8] = {2, 1, -1, -2, -2, -1, 1, 2};
    vector<vector<int>> dist(n + 1, vector<int>(n + 1, -1));
    queue<pair<int, int>> q;
    dist[r1][c1] = 0;
    q.push({r1, c1});
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int d = 0; d < 8; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 1 || ny < 1 || nx > n || ny > n || dist[nx][ny] != -1) continue;
            dist[nx][ny] = dist[x][y] + 1;
            q.push({nx, ny});
        }
    }
    cout << dist[r2][c2] << "\n";
}

Inputs 8 1 1 8 8 and 3 1 1 3 3:

6
4

On a 3 × 3 board the centre square can never be reached, but the corner (3, 3) can, in 4 jumps.

3. Print the path. Solve Courier Grid, and also print one shortest route as a string of moves (D, R, U, L).

Solution

When BFS first reaches a cell, remember which move reached it (how[nx][ny] = d). After BFS, walk back from T to S by undoing those moves, then reverse the string. The walk back is at most n·m steps.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for (auto &row : g) cin >> row;
    int sx = 0, sy = 0, tx = 0, ty = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 'S') sx = i, sy = j;
            if (g[i][j] == 'T') tx = i, ty = j;
        }
    int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
    const string name = "DRUL";                 // down, right, up, left
    vector<vector<int>> dist(n, vector<int>(m, -1)), how(n, vector<int>(m, -1));
    queue<pair<int, int>> q;
    dist[sx][sy] = 0;
    q.push({sx, sy});
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (g[nx][ny] == '#' || dist[nx][ny] != -1) continue;
            dist[nx][ny] = dist[x][y] + 1;
            how[nx][ny] = d;                    // the move that reached this cell
            q.push({nx, ny});
        }
    }
    if (dist[tx][ty] == -1) { cout << -1 << "\n"; return 0; }
    string path;
    for (int x = tx, y = ty; x != sx || y != sy; ) {   // walk back from T to S
        int d = how[x][y];
        path += name[d];
        x -= dx[d], y -= dy[d];
    }
    reverse(path.begin(), path.end());
    cout << dist[tx][ty] << " " << path << "\n";
}

The three samples of Courier Grid:

3 RRR
-1
1 R

4. Fewest turns. Grid with ., # (impassable), S and T. The rider may start facing any direction; moving one cell straight ahead is free, turning (changing direction, on the spot) costs 1. Print the fewest turns from S to T, or −1.

Solution

The cell alone is not enough: the cost of the next move depends on the direction you face. So the state is (cell, direction), 4·n·m states. Going straight is a 0-edge to (next cell, same direction), turning is a 1-edge to (same cell, other direction): 0-1 BFS on the states. This "add what matters to the state" idea is the heart of next episode's state graphs.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for (auto &row : g) cin >> row;
    int sx = 0, sy = 0, tx = 0, ty = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 'S') sx = i, sy = j;
            if (g[i][j] == 'T') tx = i, ty = j;
        }
    int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
    const int INF = 1e9;
    // state = (cell, direction we are facing); turning costs 1, going straight costs 0
    vector<vector<array<int, 4>>> dist(n, vector<array<int, 4>>(m, {INF, INF, INF, INF}));
    deque<array<int, 3>> dq;
    for (int d = 0; d < 4; d++) { dist[sx][sy][d] = 0; dq.push_back({sx, sy, d}); }   // any first direction is free
    while (!dq.empty()) {
        auto [x, y, d] = dq.front();
        dq.pop_front();
        int cur = dist[x][y][d];
        int nx = x + dx[d], ny = y + dy[d];     // go straight: cost 0
        if (nx >= 0 && ny >= 0 && nx < n && ny < m && g[nx][ny] != '#' && cur < dist[nx][ny][d]) {
            dist[nx][ny][d] = cur;
            dq.push_front({nx, ny, d});
        }
        for (int e = 0; e < 4; e++)             // turn on the spot: cost 1
            if (cur + 1 < dist[x][y][e]) {
                dist[x][y][e] = cur + 1;
                dq.push_back({x, y, e});
            }
    }
    int best = *min_element(dist[tx][ty].begin(), dist[tx][ty].end());
    cout << (best == INF ? -1 : best) << "\n";
}

Inputs 3 4 / S..# / .#.. / ...T (down two, turn once, right three) and 1 3 / S#T:

1
-1

Quick quiz

In 0-1 BFS, the cell at the front of the deque has cost 4. Which costs can be in the deque right now?

if (w == 0) dq.push_front(v);
else        dq.push_back(v);

A) any cost at all · B) only 4 · C) 4 and 5 · D) 4, 5 and 6

Answer

C. A free step from a cost-4 cell gives cost 4 and goes to the front; a wall gives 5 and goes to the back. The deque only ever holds two neighbouring costs, d and d + 1, which is why it stays sorted.

Interview questions

  1. Why does BFS give shortest paths in an unweighted graph? The queue takes nodes out in non-decreasing order of distance (all of distance d before any of d + 1), so the first time a node is reached is along a shortest path.
  2. Why not DFS? DFS commits to one branch as deep as it can. The first path it finds to a node can be much longer than the shortest; on the sample it gives 7 instead of 3.
  3. What is the time and memory of BFS? O(V + E) time and O(V) memory. On an n × m grid, O(n·m).
  4. When does recursion fail and what do you do? When the depth exceeds the stack size (often 8 MB): about 10^6 nested calls on a big grid or a long chain. Use BFS, an explicit stack, or (on some judges) raise the stack limit.
  5. What is 0-1 BFS and why is it correct? Shortest paths when every edge weight is 0 or 1, using a deque: weight-0 relaxations go to the front, weight-1 to the back. The deque always holds costs d and d + 1 in order, so it behaves like Dijkstra's priority queue in O(V + E).
  6. Adjacency list or matrix? List: O(V + E) memory, iterate neighbours in O(deg). Matrix: O(V²) memory, O(1) edge lookup; only for small dense graphs (V up to a few thousand).

Glossary

Term Meaning Example
Graph A set of nodes joined by edges villages and roads
Node (vertex) One object in a graph a village, a grid cell
Edge A link between two nodes; two-way (undirected) or one-way (directed) a road between villages 1 and 2
Neighbour A node joined to u by an edge 1 and 3 are neighbours of 2
Adjacency list For every node, the list of its neighbours adj[2] = {1, 3}
Adjacency matrix An n × n table, 1 if there is an edge too big for n = 2 · 10^5
Connected component (group) A largest set of nodes that can all reach each other {1, 2, 3}, {4, 5}, {6}
DFS (depth-first search) Visit a node, then go as deep as possible through unseen neighbours counting road groups
Seen / visited array Marks nodes already reached, so none is processed twice vector<bool> seen
Grid graph Cells as nodes, side steps as edges, never stored explicitly the courier's city
dx / dy arrays Offsets for the neighbours of a cell {1, 0, -1, 0} / {0, 1, 0, -1}
Bounds check Making sure a neighbour is inside the grid before reading it 0 <= nx && nx < n
BFS (breadth-first search) Visit nodes layer by layer from the start, using a queue Courier Grid in O(n·m)
Queue First in, first out queue<pair<int, int>> q
Layer All nodes at the same distance from the start the ring at distance 2
Shortest path A path with the fewest steps (or least total cost) S → (0,1) → (0,2) → T
Flood fill Marking every cell of one group, starting from one cell counting parts of a field
Call stack / stack frame The memory where each active function call keeps its locals 10^6 nested dfs calls
Stack overflow The call stack runs out of space; the program crashes Segmentation fault
Explicit stack A vector used as a stack instead of recursion st.push_back, st.pop_back
Heap The big memory area used by vector and other containers room for 10^6 pairs
Edge weight (cost) A number attached to an edge wall = 1, lane = 0
Deque A double-ended queue: push and pop at both ends deque<pair<int, int>> dq
0-1 BFS Shortest paths with weights 0/1: weight 0 to the front, 1 to the back Wall Breaker
Relaxation Improving a node's distance if a better path is found if (dist[x][y] + w < dist[nx][ny])
Dijkstra's algorithm Shortest paths with non-negative weights using a priority queue next episode
Priority queue A container that always gives the smallest (or largest) item priority_queue<..., greater<>>
Undefined behaviour Code whose result C++ does not define reading g[-1]
Segmentation fault (SIGSEGV) The OS stops a program that touches memory it does not own stack overflow
Wrong Answer (WA) The judge's verdict when the output differs 7 instead of 3
Runtime Error (RE) The judge's verdict when the program crashes the recursive flood fill
Stress test Comparing a fast solution with a slow, surely-correct one on random inputs all 1000 tests passed
mt19937 C++'s Mersenne Twister random generator; a fixed seed repeats the same numbers mt19937 rng(45);
State Everything that decides the future of a search, not only the position (cell, direction) in Fewest Turns

Summary

  • Store graphs as adjacency lists (O(n + m)); DFS from every unseen node counts connected components (3, 4).
  • A grid is a graph: neighbours from dx/dy, bounds check first.
  • DFS gives a path, not the shortest: 7 instead of 3, Wrong Answer.
  • BFS with a queue reaches cells in order of distance: 3, -1, 1, and 1998 on 10^6 cells in milliseconds. O(V + E).
  • Recursive flood fill on 10^6 cells: stack overflow (Segmentation fault); an explicit stack prints 1.
  • Weights 0 and 1: plain BFS prints 1 instead of 0; 0-1 BFS with a deque (0 → front, 1 → back) is right and linear (0, 1, 0, 128), and agrees with Dijkstra on 1000 random grids.

Solutions in C++, Java and Python

Problem A · Road Groups

C++ (the episode's template; for very deep graphs use the explicit-stack version below)

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> adj;
vector<bool> seen;

void dfs(int u) {
    seen[u] = true;
    for (int v : adj[u])
        if (!seen[v]) dfs(v);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    adj.assign(n + 1, {});
    seen.assign(n + 1, false);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);              // a road works both ways
        adj[b].push_back(a);
    }
    int groups = 0;
    for (int u = 1; u <= n; u++)
        if (!seen[u]) { groups++; dfs(u); }
    cout << groups << "\n";
}

Java (explicit stack: Java's default thread stack is too small for deep recursion)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        st.nextToken(); int n = (int) st.nval;
        st.nextToken(); int m = (int) st.nval;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
        for (int i = 0; i < m; i++) {
            st.nextToken(); int a = (int) st.nval;
            st.nextToken(); int b = (int) st.nval;
            adj.get(a).add(b);
            adj.get(b).add(a);
        }
        boolean[] seen = new boolean[n + 1];
        int groups = 0;
        ArrayDeque<Integer> stack = new ArrayDeque<>();   // explicit stack: no recursion depth limit
        for (int s = 1; s <= n; s++) {
            if (seen[s]) continue;
            groups++;
            seen[s] = true;
            stack.push(s);
            while (!stack.isEmpty()) {
                int u = stack.pop();
                for (int v : adj.get(u))
                    if (!seen[v]) { seen[v] = true; stack.push(v); }
            }
        }
        System.out.println(groups);
    }
}
3
4

Python (explicit stack: Python's recursion limit is about 1000)

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    adj = [[] for _ in range(n + 1)]
    for i in range(m):
        a, b = int(data[2 + 2 * i]), int(data[3 + 2 * i])
        adj[a].append(b)
        adj[b].append(a)
    seen = [False] * (n + 1)
    groups = 0
    for s in range(1, n + 1):
        if seen[s]:
            continue
        groups += 1
        seen[s] = True
        stack = [s]                      # explicit stack: Python recursion is limited to ~1000
        while stack:
            u = stack.pop()
            for v in adj[u]:
                if not seen[v]:
                    seen[v] = True
                    stack.append(v)
    print(groups)

main()
3
4

Problem G1 · Courier Grid

C++

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {1, 0, -1, 0};                 // down, right, up, left
int dy[4] = {0, 1, 0, -1};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for (auto &row : g) cin >> row;
    int sx = 0, sy = 0, tx = 0, ty = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 'S') sx = i, sy = j;
            if (g[i][j] == 'T') tx = i, ty = j;
        }
    vector<vector<int>> dist(n, vector<int>(m, -1));
    queue<pair<int, int>> q;
    dist[sx][sy] = 0;
    q.push({sx, sy});
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (g[nx][ny] == '#' || dist[nx][ny] != -1) continue;
            dist[nx][ny] = dist[x][y] + 1;    // one layer further out
            q.push({nx, ny});
        }
    }
    cout << dist[tx][ty] << "\n";
}

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());
        char[][] g = new char[n][];
        for (int i = 0; i < n; i++) g[i] = br.readLine().trim().toCharArray();
        int sx = 0, sy = 0, tx = 0, ty = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                if (g[i][j] == 'S') { sx = i; sy = j; }
                if (g[i][j] == 'T') { tx = i; ty = j; }
            }
        int[] dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
        int[][] dist = new int[n][m];
        for (int[] row : dist) Arrays.fill(row, -1);
        ArrayDeque<int[]> q = new ArrayDeque<>();
        dist[sx][sy] = 0;
        q.add(new int[]{sx, sy});
        while (!q.isEmpty()) {
            int[] c = q.poll();
            for (int d = 0; d < 4; d++) {
                int nx = c[0] + dx[d], ny = c[1] + dy[d];
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                if (g[nx][ny] == '#' || dist[nx][ny] != -1) continue;
                dist[nx][ny] = dist[c[0]][c[1]] + 1;
                q.add(new int[]{nx, ny});
            }
        }
        System.out.println(dist[tx][ty]);
    }
}
3
-1
1

Python

import sys
from collections import deque

def main():
    data = sys.stdin.read().split()
    n, m = int(data[0]), int(data[1])
    g = data[2:2 + n]
    for i in range(n):
        for j in range(m):
            if g[i][j] == 'S': sx, sy = i, j
            if g[i][j] == 'T': tx, ty = i, j
    dist = [[-1] * m for _ in range(n)]
    dist[sx][sy] = 0
    q = deque([(sx, sy)])
    while q:
        x, y = q.popleft()
        for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and g[nx][ny] != '#' and dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))
    print(dist[tx][ty])

main()
3
-1
1

Problem G2 · Wall Breaker

C++

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {1, 0, -1, 0};                 // down, right, up, left
int dy[4] = {0, 1, 0, -1};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for (auto &row : g) cin >> row;
    int sx = 0, sy = 0, tx = 0, ty = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 'S') sx = i, sy = j;
            if (g[i][j] == 'T') tx = i, ty = j;
        }
    const int INF = 1e9;
    vector<vector<int>> dist(n, vector<int>(m, INF));
    deque<pair<int, int>> dq;
    dist[sx][sy] = 0;
    dq.push_back({sx, sy});
    while (!dq.empty()) {
        auto [x, y] = dq.front();
        dq.pop_front();
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            int w = (g[nx][ny] == '#');           // a wall costs 1, a road 0
            if (dist[x][y] + w < dist[nx][ny]) {
                dist[nx][ny] = dist[x][y] + w;
                if (w == 0) dq.push_front({nx, ny});
                else dq.push_back({nx, ny});
            }
        }
    }
    cout << dist[tx][ty] << "\n";
}

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());
        char[][] g = new char[n][];
        for (int i = 0; i < n; i++) g[i] = br.readLine().trim().toCharArray();
        int sx = 0, sy = 0, tx = 0, ty = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                if (g[i][j] == 'S') { sx = i; sy = j; }
                if (g[i][j] == 'T') { tx = i; ty = j; }
            }
        int[] dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
        int[][] dist = new int[n][m];
        for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
        ArrayDeque<int[]> dq = new ArrayDeque<>();
        dist[sx][sy] = 0;
        dq.addLast(new int[]{sx, sy});
        while (!dq.isEmpty()) {
            int[] c = dq.pollFirst();
            for (int d = 0; d < 4; d++) {
                int nx = c[0] + dx[d], ny = c[1] + dy[d];
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                int w = g[nx][ny] == '#' ? 1 : 0;
                if (dist[c[0]][c[1]] + w < dist[nx][ny]) {
                    dist[nx][ny] = dist[c[0]][c[1]] + w;
                    if (w == 0) dq.addFirst(new int[]{nx, ny});
                    else dq.addLast(new int[]{nx, ny});
                }
            }
        }
        System.out.println(dist[tx][ty]);
    }
}
0
1
0

Python

import sys
from collections import deque

def main():
    data = sys.stdin.read().split()
    n, m = int(data[0]), int(data[1])
    g = data[2:2 + n]
    for i in range(n):
        for j in range(m):
            if g[i][j] == 'S': sx, sy = i, j
            if g[i][j] == 'T': tx, ty = i, j
    INF = float('inf')
    dist = [[INF] * m for _ in range(n)]
    dist[sx][sy] = 0
    dq = deque([(sx, sy)])
    while dq:
        x, y = dq.popleft()
        for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m:
                w = 1 if g[nx][ny] == '#' else 0
                if dist[x][y] + w < dist[nx][ny]:
                    dist[nx][ny] = dist[x][y] + w
                    if w == 0: dq.appendleft((nx, ny))
                    else: dq.append((nx, ny))
    print(dist[tx][ty])

main()
0
1
0