DSA sheet / Graph
Labyrinth
Do these first: Counting Rooms
The problem in brief
You get an n by m grid (up to 1000 by 1000) with walls, floor, a start cell A and an end cell B. You can move up, down, left or right through floor cells. If B is reachable print YES, the length of a shortest path, and one shortest path written as a string of the letters L, R, U, D; otherwise print NO.
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1193.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
All moves cost the same. Which traversal finds the fewest-step path in an unweighted graph?
-
Run it from A and record, for each cell, how many steps it took to get there. What tells you B is unreachable?
-
Knowing only distances is not enough to print the path. What single extra fact per cell lets you walk backwards from B to A?
-
Walking backwards produces the moves in reverse. What do you do before printing?
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
Shortest path with unit edge costs means BFS: it explores cells in order of distance, so the first time it reaches a cell is by a shortest path. That is the whole algorithm for the length. DFS would find some path, but not necessarily a shortest one.
To output the actual path, store with each cell the move that first reached it (or the parent cell). After BFS, start at B and repeatedly undo the stored move to step back toward A, collecting letters; reverse them at the end. The habit: BFS gives distances, and parent pointers turn a distance table into an actual route, so store the parent (or the move) at the moment you first discover a cell.
Take care with a grid of a million cells: use flat arrays and an iterative queue, and build the output string once. Mind that A and B are not walls, and the path can have up to about a million characters.
Intuition
Drop a stone at A and watch the ripple spread in rings. Each ring is the set of cells at the same distance. Whenever the ripple first touches a cell, remember which neighbour it came from. When it reaches B, follow those memories back to A.
Approach
- Find A and B while reading the grid.
- BFS from A with a queue. When you reach a floor/B cell for the first time, record
how[cell]= the direction letter used to enter it and mark it visited. - If B was never reached print NO.
- Otherwise rebuild the path: from B, look at
how[cell], append that letter, step to the cell you came from (opposite direction), until you are at A. Reverse the letters. - Print YES, the path length, and the path.
Pitfalls: the length is the number of moves, not the number of cells on the path; when A and B are adjacent the path is a single letter; the path can be about a million characters, so build the output once and use a flat array and a preallocated queue for speed.
Complexity
O(n * m) time and memory.
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
using namespace std;
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 start = -1, target = -1;
for (int r = 0; r < n; r++)
for (int c = 0; c < m; c++) {
if (g[r][c] == 'A') start = r * m + c;
if (g[r][c] == 'B') target = r * m + c;
}
vector<char> how(n * m, 0); // move letter used to enter each cell (0 = unvisited)
vector<int> queue(n * m);
int head = 0, tail = 0;
how[start] = 'S';
queue[tail++] = start;
const int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
const char mv[4] = {'D', 'U', 'R', 'L'};
while (head < tail && !how[target]) {
int cell = queue[head++];
int r = cell / m, c = cell % m;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= n || nc < 0 || nc >= m || g[nr][nc] == '#') continue;
int nxt = nr * m + nc;
if (how[nxt]) continue;
how[nxt] = mv[k];
queue[tail++] = nxt;
}
}
if (!how[target]) {
cout << "NO\n";
return 0;
}
string path;
int cell = target;
while (cell != start) {
char ch = how[cell];
path += ch;
int r = cell / m, c = cell % m;
if (ch == 'D') r--;
else if (ch == 'U') r++;
else if (ch == 'R') c--;
else c++;
cell = r * m + c;
}
reverse(path.begin(), path.end());
cout << "YES\n" << path.size() << "\n" << path << "\n";
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
rows = data[2:2 + n]
wall = bytearray(n * m)
start = target = -1
for r in range(n):
row = rows[r]
for c in range(m):
ch = row[c]
if ch == '#':
wall[r * m + c] = 1
elif ch == 'A':
start = r * m + c
elif ch == 'B':
target = r * m + c
how = bytearray(n * m) # move letter (as a byte) used to enter each cell; 0 = unvisited
how[start] = ord('S')
queue = [start]
head = 0
while head < len(queue) and not how[target]:
cell = queue[head]
head += 1
r, c = divmod(cell, m)
if r < n - 1 and not wall[cell + m] and not how[cell + m]:
how[cell + m] = ord('D')
queue.append(cell + m)
if r > 0 and not wall[cell - m] and not how[cell - m]:
how[cell - m] = ord('U')
queue.append(cell - m)
if c < m - 1 and not wall[cell + 1] and not how[cell + 1]:
how[cell + 1] = ord('R')
queue.append(cell + 1)
if c > 0 and not wall[cell - 1] and not how[cell - 1]:
how[cell - 1] = ord('L')
queue.append(cell - 1)
if not how[target]:
print("NO")
return
path = []
cell = target
back = {'D': -m, 'U': m, 'R': -1, 'L': 1}
while cell != start:
ch = chr(how[cell])
path.append(ch)
cell += back[ch]
path.reverse()
print("YES")
print(len(path))
print("".join(path))
main()import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
boolean[] wall = new boolean[n * m];
int start = -1, target = -1;
for (int r = 0; r < n; r++) {
String row = in.readLine();
for (int c = 0; c < m; c++) {
char ch = row.charAt(c);
if (ch == '#') wall[r * m + c] = true;
else if (ch == 'A') start = r * m + c;
else if (ch == 'B') target = r * m + c;
}
}
byte[] how = new byte[n * m]; // move letter used to enter each cell; 0 = unvisited
int[] queue = new int[n * m];
int head = 0, tail = 0;
how[start] = 'S';
queue[tail++] = start;
int[] dr = {1, -1, 0, 0}, dc = {0, 0, 1, -1};
byte[] mv = {'D', 'U', 'R', 'L'};
while (head < tail && how[target] == 0) {
int cell = queue[head++];
int r = cell / m, c = cell % m;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
int nxt = nr * m + nc;
if (wall[nxt] || how[nxt] != 0) continue;
how[nxt] = mv[k];
queue[tail++] = nxt;
}
}
if (how[target] == 0) {
System.out.println("NO");
return;
}
StringBuilder path = new StringBuilder();
int cell = target;
while (cell != start) {
char ch = (char) how[cell];
path.append(ch);
int r = cell / m, c = cell % m;
if (ch == 'D') r--;
else if (ch == 'U') r++;
else if (ch == 'R') c--;
else c++;
cell = r * m + c;
}
path.reverse();
System.out.println("YES\n" + path.length() + "\n" + path);
}
}const lines = require('fs').readFileSync(0, 'utf8').split('\n');
const [n, m] = lines[0].trim().split(/\s+/).map(Number);
const wall = new Uint8Array(n * m);
let start = -1;
let target = -1;
for (let r = 0; r < n; r++) {
const row = lines[1 + r];
for (let c = 0; c < m; c++) {
const ch = row[c];
if (ch === '#') wall[r * m + c] = 1;
else if (ch === 'A') start = r * m + c;
else if (ch === 'B') target = r * m + c;
}
}
const how = new Uint8Array(n * m); // move letter (char code) used to enter each cell; 0 = unvisited
const queue = new Int32Array(n * m);
let head = 0;
let tail = 0;
how[start] = 83; // 'S'
queue[tail++] = start;
const dr = [1, -1, 0, 0];
const dc = [0, 0, 1, -1];
const mv = ['D', 'U', 'R', 'L'].map((s) => s.charCodeAt(0));
while (head < tail && how[target] === 0) {
const cell = queue[head++];
const r = Math.floor(cell / m);
const c = cell - r * m;
for (let k = 0; k < 4; k++) {
const nr = r + dr[k];
const nc = c + dc[k];
if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
const nxt = nr * m + nc;
if (wall[nxt] || how[nxt] !== 0) continue;
how[nxt] = mv[k];
queue[tail++] = nxt;
}
}
if (how[target] === 0) {
console.log('NO');
} else {
const path = [];
let cell = target;
const back = { D: -m, U: m, R: -1, L: 1 };
while (cell !== start) {
const ch = String.fromCharCode(how[cell]);
path.push(ch);
cell += back[ch];
}
path.reverse();
console.log(`YES\n${path.length}\n${path.join('')}`);
}Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).