Summary

This problem asks us to count how many times a given word appears in a grid of uppercase letters.

The word can appear in two ways:

• Straight line

The letters appear in sequence in one horizontal, vertical, or diagonal direction.

• Right-angle bend

The word is split into two straight segments. The first segment follows one direction, then the second segment continues in a perpendicular direction, forming a right angle at the turning letter.

The key idea is to check every starting cell, every direction, and every possible turning point.

This is a grid search problem with direction vectors and careful boundary checking.

Understanding the Problem

We are given:

• a word W
• the number of rows R
• the number of columns C
• an R x C grid of uppercase letters

The output is the total number of hidden occurrences of W.

The word must be read in order. A valid occurrence may be:

1. entirely straight
2. partly straight, then turned 90 degrees once

For example, if the word is HELLO, a bent occurrence might split at different positions:

H | ELLO
HE | LLO
HEL | LO
HELL | O

However, in this problem, both line segments should contain at least one movement. That means the turning point cannot be the starting letter or the final letter.

A single grid letter can be used in more than one occurrence. We are counting all valid occurrences, not marking letters as unavailable.

Input Specification

The input contains:

• line 1: the word W
• line 2: integer R, the number of rows
• line 3: integer C, the number of columns
• next R lines: C uppercase letters separated by spaces

The word has distinct uppercase letters and length at least 2.

Core DSA Concepts Involved

• Grid Traversal

Try each cell as a possible starting point.

• Direction Vectors

Represent movement using (dr, dc) pairs.

• Brute Force with Small Branching

For each start, try all directions and possible turn positions.

• Geometry in Code

A right-angle turn can be represented by moving to one of two perpendicular directions.

• Boundary Checking

Every cell visited by a candidate word must stay inside the grid.

Direction Model

We use 8 directions in circular order:

E, NE, N, NW, W, SW, S, SE

In Python:

dirs = [
    (0, 1),    # E
    (-1, 1),   # NE
    (-1, 0),   # N
    (-1, -1),  # NW
    (0, -1),   # W
    (1, -1),   # SW
    (1, 0),    # S
    (1, 1)     # SE
]

This ordering makes perpendicular directions easy.

If the first direction has index d, the two perpendicular directions are:

(d + 2) % 8
(d - 2) % 8

For example:

• east can turn north or south
• northeast can turn northwest or southeast
• north can turn west or east

Approach

We count two kinds of matches.

1. Straight-Line Search

For each starting cell:

• try all 8 directions
• check whether every character of W matches while walking in that direction
• if the full word matches, add 1 to the answer

2. Right-Angle Search

For each starting cell:

• choose a first direction d1
• choose one of the two perpendicular directions d2
• choose a turning point turn_at
• check whether:

W[0] ... W[turn_at]

matches along d1, and:

W[turn_at + 1] ... W[L - 1]

matches along d2, starting from the turning letter.

The turning point is included in the first segment. The second segment starts one step away from the turning point.

For a word of length L, the valid turning points are:

1, 2, ..., L - 2

This ensures that both segments have at least one movement.

Helper Functions

We use three helper functions:

• inside(r, c)

Checks whether (r, c) is inside the grid.

• match_straight(r, c, dr, dc)

Checks whether the full word appears from (r, c) in one direction.

• match_bend(r, c, d1, d2, turn_at)

Checks whether the word appears using one first direction, one perpendicular second direction, and one chosen turning point.

This keeps the main loop easy to read.

Python Solution

# CCC 2023 J5 - CCC Word Hunt
# Straight-line and one-bend grid search

W = input().strip()
L = len(W)

R = int(input())
C = int(input())

grid = [input().split() for _ in range(R)]

# 8 directions in circular order so perpendicular turns are +/- 2
dirs = [
    (0, 1),    # E
    (-1, 1),   # NE
    (-1, 0),   # N
    (-1, -1),  # NW
    (0, -1),   # W
    (1, -1),   # SW
    (1, 0),    # S
    (1, 1)     # SE
]


def inside(r, c):
    return 0 <= r < R and 0 <= c < C


def match_straight(r, c, dr, dc):
    # Match W[0..L-1] starting at (r, c), stepping by (dr, dc)
    for k in range(L):
        nr = r + dr * k
        nc = c + dc * k

        if not inside(nr, nc) or grid[nr][nc] != W[k]:
            return False

    return True


def match_bend(r, c, d1, d2, turn_at):
    """
    First segment:
      W[0..turn_at] along direction d1, including the turning letter.

    Second segment:
      W[turn_at+1..L-1] along direction d2, starting one step after
      the turning letter.
    """
    dr1, dc1 = dirs[d1]
    dr2, dc2 = dirs[d2]

    # Check the first segment, including the turning point.
    for k in range(turn_at + 1):
        nr = r + dr1 * k
        nc = c + dc1 * k

        if not inside(nr, nc) or grid[nr][nc] != W[k]:
            return False

    # Turning point location.
    pr = r + dr1 * turn_at
    pc = c + dc1 * turn_at

    # Check the second segment.
    for k in range(turn_at + 1, L):
        step = k - turn_at
        nr = pr + dr2 * step
        nc = pc + dc2 * step

        if not inside(nr, nc) or grid[nr][nc] != W[k]:
            return False

    return True


count = 0

for r in range(R):
    for c in range(C):
        if grid[r][c] != W[0]:
            continue

        # 1. Straight-line matches
        for d in range(8):
            dr, dc = dirs[d]
            if match_straight(r, c, dr, dc):
                count += 1

        # 2. One-bend matches
        for d1 in range(8):
            for d2 in ((d1 + 2) % 8, (d1 - 2) % 8):
                for turn_at in range(1, L - 1):
                    if match_bend(r, c, d1, d2, turn_at):
                        count += 1

print(count)

C++ Solution

// CCC 2023 J5 - CCC Word Hunt
// Straight-line and one-bend grid search

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int R, C;
string W;
int L;

// 8 directions in circular order so perpendicular turns are +/- 2
int dr[8] = {0, -1, -1, -1, 0, 1, 1, 1};
int dc[8] = {1,  1,  0, -1, -1, -1, 0, 1};

bool inside(int r, int c) {
    return 0 <= r && r < R && 0 <= c && c < C;
}

bool matchStraight(const vector<vector<char>>& grid, int r, int c, int d) {
    // Match W[0..L-1] starting at (r, c), stepping in direction d.
    for (int k = 0; k < L; k++) {
        int nr = r + dr[d] * k;
        int nc = c + dc[d] * k;

        if (!inside(nr, nc) || grid[nr][nc] != W[k]) {
            return false;
        }
    }

    return true;
}

bool matchBend(const vector<vector<char>>& grid, int r, int c,
               int d1, int d2, int turnAt) {
    // Check first segment, including the turning point.
    for (int k = 0; k <= turnAt; k++) {
        int nr = r + dr[d1] * k;
        int nc = c + dc[d1] * k;

        if (!inside(nr, nc) || grid[nr][nc] != W[k]) {
            return false;
        }
    }

    // Turning point location.
    int pr = r + dr[d1] * turnAt;
    int pc = c + dc[d1] * turnAt;

    // Check second segment, starting one step after the turning point.
    for (int k = turnAt + 1; k < L; k++) {
        int step = k - turnAt;
        int nr = pr + dr[d2] * step;
        int nc = pc + dc[d2] * step;

        if (!inside(nr, nc) || grid[nr][nc] != W[k]) {
            return false;
        }
    }

    return true;
}

int main() {
    cin >> W;
    L = (int)W.size();

    cin >> R;
    cin >> C;

    vector<vector<char>> grid(R, vector<char>(C));

    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            cin >> grid[r][c];
        }
    }

    int count = 0;

    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            if (grid[r][c] != W[0]) {
                continue;
            }

            // 1. Straight-line matches
            for (int d = 0; d < 8; d++) {
                if (matchStraight(grid, r, c, d)) {
                    count++;
                }
            }

            // 2. One-bend matches
            for (int d1 = 0; d1 < 8; d1++) {
                int d2a = (d1 + 2) % 8;
                int d2b = (d1 + 6) % 8; // same as (d1 - 2 + 8) % 8

                for (int turnAt = 1; turnAt <= L - 2; turnAt++) {
                    if (matchBend(grid, r, c, d1, d2a, turnAt)) {
                        count++;
                    }

                    if (matchBend(grid, r, c, d1, d2b, turnAt)) {
                        count++;
                    }
                }
            }
        }
    }

    cout << count << '\n';

    return 0;
}

Complexity Analysis

Let:

L = length of the word

For each grid cell, we try:

• 8 straight directions
• 8 first directions for bent words
• 2 perpendicular second directions
• up to L - 2 possible turning points

Each check may scan up to L letters.

So a clear upper bound is:

O(R * C * 8 * L^2)

Since the word length is small in this problem, this approach is efficient and easy to reason about.

The extra space used is:

O(1)

apart from the input grid.

Common Mistakes

• Only checking straight lines

The full problem allows one right-angle bend.

• Turning in non-perpendicular directions

A valid bend must form a right angle. From direction d, only (d + 2) % 8 and (d - 2) % 8 are allowed.

• Letting the turn happen at the first or last letter

That can create duplicate counting or an empty second segment. Use turn_at from 1 to L - 2.

• Forgetting diagonal directions

The word can appear horizontally, vertically, or diagonally.

• Mixing up the pivot letter

The turning letter belongs to the first segment. The second segment starts one step after the pivot.

• Using a visited set

This is not a pathfinding problem where cells become unavailable. A grid letter may be used in more than one occurrence.

Learning Outcomes

This problem is good practice for:

• scanning a grid systematically
• representing directions with arrays
• converting geometry rules into index movement
• writing helper functions for cleaner brute force
• avoiding double-counting in search problems

The most important implementation idea is the turning point:

turn_at = the index of the letter where the path changes direction

Once we choose the starting cell, first direction, second direction, and turning point, the whole path is fixed. Then we only need to check whether the letters match.

Practice Questions

1. Why do we need 8 directions instead of 4?
2. Why are perpendicular directions two positions away in the circular direction list?
3. Why should turn_at start at 1?
4. Why should turn_at stop at L - 2?
5. What would change if the word were allowed to turn more than once?