A: Chessboard Rook Placement
Given an (n \times n) board where certain positions marked # allow placement, determine the number of ways to place (k) identical, non-attacking rooks. Constraints: (k \leq n \leq 8).
Since each row can hold at most one rook, a depth-first search over rows is feasible. The state space is bounded by ((n+1)^n), at most about (4 \times 10^7) in the worst case when (n=8). Each recursive step performs constant-time work, giving a similar time complexity upper bound.
We define a recursive function search(row, placed) where row is the current row index and placed is the number of rooks already set. At each row, we either skip it or place a rook in an allowed, unoccupied column. A boolean array tracks used columns.
#include <cstdio>
int n, k;
char board[10][10];
int colUsed[10];
int countWays(int r, int placed) {
if (placed == k) return 1;
if (r > n) return 0;
int total = 0;
for (int c = 1; c <= n; ++c) {
if (!colUsed[c] && board[r][c] == '#') {
colUsed[c] = 1;
total += countWays(r + 1, placed + 1);
colUsed[c] = 0;
}
}
total += countWays(r + 1, placed);
return total;
}
B: 3D Dungeon Escape
Navigate a 3D grid with obstacles from start S to exit E. Each cell is either passible or blocked (#). Output the shortest path length or a trapped message.
Using BFS with six directional offsets (one cooordinate changes by ±1, others remain 0) yields a runtime bounded by the grid volume, (O(LRC) \le 30^3 \approx 3 \times 10^4).
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
struct Cell { int x, y, z, d; };
int L, R, C, vis[32][32][32];
char vol[32][32][32];
int dx[] = {0, 0, 0, 0, 1, -1};
int dy[] = {0, 0, 1, -1, 0, 0};
int dz[] = {1, -1, 0, 0, 0, 0};
int bfs(Cell st) {
queue<Cell> q;
q.push(st);
vis[st.x][st.y][st.z] = 1;
while (!q.empty()) {
Cell cur = q.front(); q.pop();
if (vol[cur.x][cur.y][cur.z] == 'E') return cur.d;
for (int i = 0; i < 6; ++i) {
int nx = cur.x + dx[i], ny = cur.y + dy[i], nz = cur.z + dz[i];
if (nx < 1 || nx > L || ny < 1 || ny > R || nz < 1 || nz > C) continue;
if (vis[nx][ny][nz] || vol[nx][ny][nz] == '#') continue;
vis[nx][ny][nz] = 1;
q.push({nx, ny, nz, cur.d + 1});
}
}
return -1;
}
C: From N to K on a Number Line
Start at (N), goal is (K) with moves (X-1), (X+1), (2X). Both (N, K) lie in ([0, 10^5]). BFS guarantees shortest steps. The visited range can be proved to stay within ([0, 10^5]) because overshooting beyond (10^5) by (2t) is never better than adjusting before doubling.
#include <cstdio>
#include <queue>
using namespace std;
const int MAX = 100001;
int vis[MAX];
int main() {
int N, K;
scanf("%d%d", &N, &K);
queue<pair<int, int>> q;
q.push({N, 0});
vis[N] = 1;
while (!q.empty()) {
auto [u, t] = q.front(); q.pop();
if (u == K) { printf("%d\n", t); return 0; }
if (u - 1 >= 0 && !vis[u - 1]) { vis[u - 1] = 1; q.push({u - 1, t + 1}); }
if (u + 1 < MAX && !vis[u + 1]) { vis[u + 1] = 1; q.push({u + 1, t + 1}); }
if (u * 2 < MAX && !vis[u * 2]) { vis[u * 2] = 1; q.push({u * 2, t + 1}); }
}
}
D: Flip Tiles with Least Presses
Given an (N \times M) binary grid (1 = black, 0 = white), pressing a cell flips itself and its orthogonal neighbours. Output a press matrix that yields all-white with minimal total presses; ties break lexicographically.
Flipping problem can be modelled by fixing the first row's press pattern, then greedily extending downwards. Each lower-row press is determined by whether the cell above is black. Time complexity is (O(2^M \cdot N)).
#include <cstdio>
#include <cstring>
int N, M, best = 1e9;
int g[16][16], press[16][16], ans[16][16], temp[16][16];
int dr[] = {0, 1, 0, -1}, dc[] = {1, 0, -1, 0};
void apply(int r, int c, int arr[16][16]) {
arr[r][c] ^= 1;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 1 && nr <= N && nc >= 1 && nc <= M)
arr[nr][nc] ^= 1;
}
}
void solve(int mask) {
memcpy(temp, g, sizeof(temp));
memset(press, 0, sizeof(press));
int cnt = 0;
for (int j = 0; j < M; j++)
if (mask & (1 << j)) {
apply(1, j + 1, temp);
press[1][j + 1] = 1;
cnt++;
}
for (int i = 2; i <= N; i++)
for (int j = 1; j <= M; j++)
if (temp[i - 1][j]) {
apply(i, j, temp);
press[i][j] = 1;
cnt++;
}
int ok = 1;
for (int j = 1; j <= M; j++)
if (temp[N][j]) ok = 0;
if (ok && cnt < best) {
best = cnt;
memcpy(ans, press, sizeof(ans));
}
}
E: Constructing Binary Multiples
Given (n \le 200), find a decimal number composed only of digits 0 and 1 that is a multiple of (n) and has at most 100 digits.
A naive BFS expanding prefixes risks exponential explosion. The correct pruning uses modulo equivalence: only keep one node per remainder modulo (n). Since there are at most (n) distinct remainders, the BFS tree has (O(n)) nodes. Each transition performs big-integer modulo in (O(n)) time, leading to (O(n^2)) total.
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int mod(const string &s, int m) {
int r = 0;
for (char c : s) r = (r * 10 + c - '0') % m;
return r;
}
void bfs(int n) {
int vis[200] = {0};
queue<string> q;
q.push("1");
vis[1 % n] = 1;
while (!q.empty()) {
string cur = q.front(); q.pop();
for (char d = '0'; d <= '1'; ++d) {
string nxt = cur + d;
int rem = mod(nxt, n);
if (rem == 0) {
cout << nxt << '\n';
return;
}
if (!vis[rem]) {
vis[rem] = 1;
q.push(nxt);
}
}
}
}
F: Prime Digit Transformations
Two 4-digit primes (N), (M). Change one digit at a time, keeping the number prime each step. Find minimum steps.
Precompute primes up to 9999. BFS up to ~1061 four-digit primes. Each number has up to 36 neighbours. Complexity per query is about (10^4 \times 36), well within limits.
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int prime[10001], vis[10001];
int bfs(int src, int dst) {
memset(vis, 0, sizeof(vis));
queue<pair<int, int>> q;
q.push({src, 0});
vis[src] = 1;
while (!q.empty()) {
auto [x, stp] = q.front(); q.pop();
if (x == dst) return stp;
int p = 1;
for (int i = 0; i < 4; i++, p *= 10) {
int d = (x / p) % 10;
int lo = (i == 3) ? 1 : 0;
for (int nd = lo; nd <= 9; nd++) {
if (nd == d) continue;
int nx = x + (nd - d) * p;
if (prime[nx] == nx && !vis[nx]) {
vis[nx] = 1;
q.push({nx, stp + 1});
}
}
}
}
return -1;
}
G: Shuffling Cards to Target Sequence
Given two piles of length (n), repeatedly interleave them as (b_1, a_1, b_2, a_2, \dots), then split the result into two halves again. Find how many operations until the sequence matches a given target.
The process can be described by permutation (f(i) = 2i \bmod (2n+1)). The order of (f) divides (\varphi(2n+1)), which is less than (2n). Simulating until identity gives worst-case (O(n^2)) per test.
#include <iostream>
#include <string>
#include <set>
using namespace std;
int solve(int n, string s1, string s2, string target) {
string cur = s1 + s2;
set<string> seen;
for (int step = 1; step <= 2 * n; ++step) {
string nxt(2 * n, ' ');
for (int i = 0; i < n; ++i) {
nxt[2 * i] = cur[n + i];
nxt[2 * i + 1] = cur[i];
}
cur = nxt;
if (cur == target) return step;
if (seen.count(cur)) return -1;
seen.insert(cur);
}
return -1;
}
H: Measuring Water with Two Jugs
Jugs of capacities (A) and (B) liters. Operations: fill, empty, pour. Find the shortest sequence leaving exactly (C) liters in one jug. States ((x, y)) total at most (A \cdot B \le 10^4). Six branch operations per state, BFS naturally yields shortest sequence.
#include <cstdio>
#include <queue>
#include <stack>
using namespace std;
struct State { int a, b, id, step; };
int A, B, C, T = 1, fa[11001], op[11001];
int vis[101][101];
char* action[] = {"FILL(1)","FILL(2)","DROP(1)","DROP(2)",
"POUR(1,2)","POUR(2,1)"};
void bfs() {
queue<State> q;
q.push({0, 0, T, 0});
vis[0][0] = T;
fa[T] = -1;
++T;
while (!q.empty()) {
auto [x, y, id, s] = q.front(); q.pop();
if (x == C || y == C) {
printf("%d\n", s);
stack<int> stk;
for (int cur = id; cur != 1; cur = fa[cur]) stk.push(cur);
while (!stk.empty()) {
puts(action[op[stk.top()]]);
stk.pop();
}
return;
}
auto add = [&](int nx, int ny, int act) {
if (!vis[nx][ny]) {
vis[nx][ny] = T;
fa[T] = id;
op[T] = act;
q.push({nx, ny, T, s + 1});
++T;
}
};
add(A, y, 0); add(x, B, 1); add(0, y, 2); add(x, 0, 3);
int mv = min(x, B - y); add(x - mv, y + mv, 4);
mv = min(y, A - x); add(x + mv, y - mv, 5);
}
puts("impossible");
}
I: Escape the Spreading Fire
Grid with walls, a person J, and multiple fire sources F. Fire spreads to four neighbours each second; the person moves similarly. Fire moves first in each second. BFS with a two-level queue (fires before person) finds the earliest exit step.
#include <cstdio>
#include <queue>
using namespace std;
int R, C, vis[1002][1002];
char g[1002][1002];
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
struct Cell { int x, y, type, t; };
int bfs() {
queue<Cell> q;
for (int i = 1; i <= R; i++)
for (int j = 1; j <= C; j++) {
vis[i][j] = 0;
if (g[i][j] == 'F') { q.push({i, j, 0, 0}); vis[i][j] = 1; }
}
for (int i = 1; i <= R; i++)
for (int j = 1; j <= C; j++)
if (g[i][j] == 'J') { q.push({i, j, 1, 0}); vis[i][j] = 1; }
while (!q.empty()) {
auto [x, y, type, t] = q.front(); q.pop();
if ((x == 1 || x == R || y == 1 || y == C) && type == 1)
return t + 1;
for (int k = 0; k < 4; k++) {
int nx = x + dx[k], ny = y + dy[k];
if (nx < 1 || nx > R || ny < 1 || ny > C) continue;
if (g[nx][ny] == '#' || vis[nx][ny]) continue;
vis[nx][ny] = 1;
q.push({nx, ny, type, t + 1});
}
}
return -1;
}
J: Shortest Path on a 5×5 Maze
Find any shortest path from top-left to bottom-right on a 5×5 grid. BFS with parent pointers and coordinates stored for reconstruction.
#include <cstdio>
#include <queue>
#include <stack>
using namespace std;
int maze[6][6], vis[6][6], T, prnt[36], posr[36], posc[36];
int dr[] = {0, 1, 0, -1}, dc[] = {1, 0, -1, 0};
int main() {
for (int i = 1; i <= 5; i++)
for (int j = 1; j <= 5; j++) scanf("%d", &maze[i][j]);
queue<pair<int, int>> q;
q.push({1, 1});
vis[1][1] = ++T;
posr[T] = 1; posc[T] = 1; prnt[T] = -1;
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
if (r == 5 && c == 5) {
stack<int> st;
for (int cur = vis[r][c]; cur != -1; cur = prnt[cur]) st.push(cur);
while (!st.empty()) {
printf("(%d, %d)\n", posr[st.top()] - 1, posc[st.top()] - 1);
st.pop();
}
return 0;
}
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 1 || nr > 5 || nc < 1 || nc > 5) continue;
if (maze[nr][nc] || vis[nr][nc]) continue;
vis[nr][nc] = ++T;
posr[T] = nr; posc[T] = nc; prnt[T] = vis[r][c];
q.push({nr, nc});
}
}
}
K: Counting Oil Deposits
Input with @ (oil) and * (rock). Eight-directionally connected oil pockets count as one deposit. DFS/BFS flood-fill with direct modification of the grid.
#include <cstdio>
int m, n, cnt;
char field[102][102];
int dr[] = {0, 1, 0, -1, 1, 1, -1, -1};
int dc[] = {1, 0, -1, 0, 1, -1, -1, 1};
void dfs(int r, int c) {
field[r][c] = '*';
for (int i = 0; i < 8; i++) {
int nr = r + dr[i], nc = c + dc[i];
if (nr >= 1 && nr <= m && nc >= 1 && nc <= n && field[nr][nc] == '@')
dfs(nr, nc);
}
}
typedef long long i64;
int main() {
while (scanf("%d%d", &m, &n), m) {
for (int i = 1; i <= m; i++) scanf("%s", &field[i][1]);
cnt = 0;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (field[i][j] == '@') { dfs(i, j); cnt++; }
printf("%d\n", cnt);
}
}
L: Splitting a Cola
Volume (S), cup capacities (A, B) with (S=A+B). Find minimum number of pours to leave exactly (S/2) in the larger cup and the bottle. A 3D BFS over states ((x, y, z)) with up to (10^6) nodes and 6 transitions.
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int S, A, B, vis[101][101][101];
struct Node { int s, a, b, step; };
int bfs() {
memset(vis, 0, sizeof(vis));
queue<Node> q;
q.push({S, 0, 0, 0});
vis[S][0][0] = 1;
while (!q.empty()) {
auto [x, y, z, st] = q.front(); q.pop();
if (x == S / 2 && y == S / 2) return st;
auto pour = [&](int src, int cap, int &a, int &b) {
int mv = min(src, cap);
a -= mv; b += mv;
};
int nx, ny, nz;
auto tryMove = [&](int xx, int yy, int zz) {
if (!vis[xx][yy][zz]) {
vis[xx][yy][zz] = 1;
q.push({xx, yy, zz, st + 1});
}
};
nx = x; ny = y; nz = z; pour(nx, A, nx, ny); tryMove(nx, ny, nz);
nx = x; ny = y; nz = z; pour(nx, B, nx, nz); tryMove(nx, ny, nz);
nx = x; ny = y; nz = z; pour(ny, S - nx, ny, nx); tryMove(nx, ny, nz);
nx = x; ny = y; nz = z; pour(ny, B - nz, ny, nz); tryMove(nx, ny, nz);
nx = x; ny = y; nz = z; pour(nz, S - nx, nz, nx); tryMove(nx, ny, nz);
nx = x; ny = y; nz = z; pour(nz, A - ny, nz, ny); tryMove(nx, ny, nz);
}
return -1;
}
M: Y and M Meeting at a Cafe
Two people at Y and M want to meet at any @. Compute the minimal sum of shortest distances. BFS from each source once stores distances to all @ spots. Final answer multiplied by 11.
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int n, m, dist[2][202][202];
char mp[202][202];
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
void bfs(int sr, int sc, int id) {
int vis[202][202] = {0};
queue<pair<int, int>> q;
q.push({sr, sc});
vis[sr][sc] = 1;
dist[id][sr][sc] = 0;
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
for (int k = 0; k < 4; k++) {
int nr = r + dx[k], nc = c + dy[k];
if (nr < 1 || nr > n || nc < 1 || nc > m) continue;
if (vis[nr][nc] || mp[nr][nc] == '#') continue;
vis[nr][nc] = 1;
dist[id][nr][nc] = dist[id][r][c] + 1;
q.push({nr, nc});
}
}
}
N: Surface Area of 3D Model
Given occupied cells in a 3D grid (N \times M \times H), compute the exterior surface area. Add a virtual bounding shell, flood-fill from outside (marking visited cells as 2). Each contact with an occupied cell (1) increments area.
#include <cstdio>
#include <queue>
using namespace std;
int N, M, H, n;
int g[62][62][62];
int dx[] = {0, 1, 0, -1, 0, 0},
dy[] = {1, 0, -1, 0, 0, 0},
dz[] = {0, 0, 0, 0, 1, -1};
int bfs() {
int area = 0;
queue<tuple<int, int, int>> q;
g[0][0][0] = 2;
q.push({0, 0, 0});
while (!q.empty()) {
auto [x, y, z] = q.front(); q.pop();
for (int k = 0; k < 6; k++) {
int nx = x + dx[k], ny = y + dy[k], nz = z + dz[k];
if (nx < 0 || nx > N+1 || ny < 0 || ny > M+1 || nz < 0 || nz > H+1)
continue;
if (g[nx][ny][nz] == 2) continue;
if (g[nx][ny][nz] == 1) area++;
else if (g[nx][ny][nz] == 0) {
g[nx][ny][nz] = 2;
q.push({nx, ny, nz});
}
}
}
return area;
}
O: Enclosing Colour Shells
An (n \times m) grid has background colour 0 and some regions coloured 1. Count the number of connected components of colour 1 that are completely surrounded by colour 0 (outer shells). We add an outer background boundary (colour 2), flood-fill through 8-connected background to mark exterior, then count 4-connected untouched colour-1 regions.
#include <cstdio>
#include <queue>
using namespace std;
int n, m;
char g[53][53];
int dr8[] = {0, 1, 0, -1, 1, 1, -1, -1};
int dc8[] = {1, 0, -1, 0, 1, -1, -1, 1};
void exteriorFill() {
queue<pair<int, int>> q;
g[0][0] = '2';
q.push({0, 0});
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
for (int i = 0; i < 8; i++) {
int nr = r + dr8[i], nc = c + dc8[i];
if (nr < 0 || nr > n+1 || nc < 0 || nc > m+1) continue;
if (g[nr][nc] == '1' || g[nr][nc] == '2') continue;
g[nr][nc] = '2';
q.push({nr, nc});
}
}
}
void colourComponent(int sr, int sc) {
queue<pair<int, int>> q;
q.push({sr, sc});
g[sr][sc] = '3';
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int nr = r + dr8[i], nc = c + dc8[i];
if (nr < 1 || nr > n || nc < 1 || nc > m) continue;
if (g[nr][nc] == '2' || g[nr][nc] == '3') continue;
g[nr][nc] = '3';
q.push({nr, nc});
}
}
}