Module assignment: word search with a path report

Why this assignment

This assignment brings the whole module together. You will read input, walk a grid with recursion, undo each step as you back out of a dead end, and print a report. The same three ideas appear in every part of the module. The base case decides when a search has succeeded or failed. The choice-and-undo step keeps the shared state clean. The row-major scan is the outer loop that turns one search into a complete answer.

A word search is a puzzle with a grid of letters and a list of words. A word is in the grid when you can spell it by moving from one cell to a neighboring cell, and you cannot use the same cell twice. Neighbors are the cells directly above, below, left or right. Diagonal moves do not count. A search program must find each word, or say that it is missing, and say where it starts.

Work through the steps in order. Each step adds one idea, and each step has a runnable block you can type into the editor. The reference solution is hidden at the end, so try the problem yourself first.

The brief

Write a C++ program that reads a letter grid and a list of words. For each word, print one line. If the word can be spelled in the grid, print its start cell. If it cannot, print NO.

The program must follow these rules.

• A word is found when you can spell it by moving from cell to adjacent cell, where adjacent means up, down, left or right.
• A path may not use the same cell twice in one word.
• The start cell is the first cell, scanning row by row from the top, from which the word can be spelled.
• The output lines are in the same order as the words in the input.

The rules say nothing about the order in which you try the four directions. That is deliberate. Whether a word exists does not depend on the direction order, and the start cell is defined by the row-major scan, so the output is the same no matter which direction you try first.

Input and output

The input has four parts, in this order.

1. A line with two numbers, R and C. R is the number of rows and C is the number of columns. Both are from 1 to 8.
2. R lines, each with exactly C lowercase letters. This is the grid.
3. A line with one number, W, the count of words. W is from 1 to 10.
4. W lines, each with one word of lowercase letters, 1 to 10 characters long.

The output has W lines. Each line has the word, then either NO, or YES followed by the row and column of the start cell. Rows and columns start from 0. Use single spaces, and do not print any extra blank lines.

Here is an example. Type it into the Input box exactly as written.

3 4
cafe
oxbz
dogm
4
cafe
good
dog
fox

The output should be:

cafe YES 0 0
good NO
dog YES 2 0
fox NO

Check the first line by hand. The word cafe runs along the top row, from column 0 to column 3, so the start cell is row 0, column 0. The word good needs two o cells that touch. The grid has an o in row 1, column 0 and another in row 2, column 1. Those two touch only on a diagonal, and diagonals do not count. The word dog starts at the first d in row-major order, which is row 2, column 0. The word fox has no f next to an o, so the answer is NO.

Requirements checklist

Use this checklist while you write the program. Tick each item when you have tested it.

• Reads R, C, the R grid rows, W and the W words, in that order.
• Treats up, down, left and right as adjacent, and never treats diagonals as adjacent.
• Never uses the same cell twice in one path.
• Tries start cells in row-major order and reports the first start that works.
• Prints NO when no start cell works.
• Prints the words in input order, one line each, with single spaces.
• Undoes its visited mark before returning from a dead end.
• Works on a grid with one row and one column.
• Handles a word longer than the number of cells in the grid, without crashing.

Grading rubric

Your solution is graded on the output for a hidden set of inputs. The rubric describes what each level of work looks like.

60 percent. The program reads the input correctly. It prints YES or NO for each word, and it is correct for words that start at the top left cell. The output format is right for the cases it handles. The program may print the wrong start cell, or it may miss starts further down the grid. It may also reuse a cell in some paths.

80 percent. The program is correct on every input in the brief. It tries every start cell in row-major order, prints the first start that works, never reuses a cell, and undoes its marks. It is correct on the sample and on the edge cases in the test list at the end of this lesson. It may be slow on the largest grids.

100 percent. The program meets every item on the checklist. It rejects impossible words quickly, for example a word with a letter that is not in the grid, or a word longer than the grid has cells. It runs well inside one second on an 8 by 8 grid with 10 words of length 10. Its code is clear: the direction list and the undo are visible, and a reader can see why each step is there.

Step 1: read the input

Start by reading the input and printing what you read. This step checks that your reading order is right before any search happens. Type the sample input from the Input and output section.

The output for the sample input is:

rows 3 cols 4
cafe
oxbz
dogm
word cafe length 4
word good length 4
word dog length 3
word fox length 3

The grid is read with cin >> grid[i], which reads one word at a time. Each grid row has no spaces, so reading a word reads the whole row. The count W comes after the grid, so read it after the last row. If you read the words before the count, the program gets the wrong values.

Step 2: search from one start cell

Now write the search. The function dfs tries to spell the word from one cell. The index k says which letter of the word the current cell must match. The base case is the last letter, which means the path is complete. The recursion moves to each neighbor that is inside the grid and not yet on the path. Read the comments, because the undo is the step most people miss.

This program is a test harness. It reads one word, and it tests the start cell (0, 0) only. The Input box needs the grid and then one word, with no count.

Type this into the Input box, which is the sample grid and then the single word cafe:

3 4
cafe
oxbz
dogm
cafe

The output is:

cafe from (0,0): YES

Trace the first two letters. The call dfs(0, 0, "cafe", 0) checks that the cell (0, 0) holds c, which it does. It marks the cell as seen. Then it tries the neighbors. Up is off the grid, so it is skipped. Down is cell (1, 0), which holds o, and that is not the a the word needs, so the call returns false and the loop moves on. Left is off the grid. Right is cell (0, 1), which holds a. The call recurses with k equal to 1, the cell matches, and the search goes on through f and e. When the call reaches the last letter, it returns true, and each caller undoes its mark and passes true up.

Now try the word good from the same cell. The output would be good from (0,0): NO, because (0, 0) holds c, not g. The first check fails at once. This is the base case at its simplest: a cell that does not match the letter returns false without marking anything.

Notice the order of the two undo lines. The undo before return true is not required for the answer, but it keeps seen clean. Each call restores seen to the same state it had when the call started, whether it succeeds or fails. That habit makes the code easy to trust.

The animation above shows a depth-first search on a graph. A grid is a graph where each cell is a node and each neighbor is an edge, so the same walk applies. Step through it and find the moment the search backs out of a dead end and tries the next neighbor.

Step 3: scan every start cell

A single start is not enough. The word may start anywhere in the grid. The next step loops over every cell in row-major order, which is row 0 left to right, then row 1 left to right, and so on. The first cell where dfs returns true is the answer. This step uses the same dfs as before, with the loop added to main. The Input box needs the grid and one word, dog.

Type the sample grid and the word dog. The output is:

dog YES 2 0

Scan the cells in order. Row 0 has c, a, f, e, and none is a d, so dfs returns false at once for each. Row 1 has o, x, b, z, and again none is a d. Row 2 has d at column 0. The call dfs(2, 0, "dog", 0) matches the d. The first neighbor it tries is up, at (1, 0). That cell holds an o, so the call goes there, but no g touches it, so that branch fails and is undone. The search then tries right, at (2, 1), which holds an o, and then (2, 2), which holds a g. That is the last letter, so the call returns true, and the program prints the start cell (2, 0).

Two details matter. The return 0; inside the loop stops the program at the first match, which is what "first start" means. And the final line, NO, is printed only when every cell has been tried. Printing NO inside the loop would be a common mistake, because it would print before the other cells had a chance to match.

Now test a word that is not in the grid, such as fox. The output is fox NO. Every cell is tried, and none starts a path that spells the word.

Step 4: the full program

The last step reads all the words in one run. It prints one line per word, in input order. It uses the search from Step 3 for each word, and it handles the complete input format from the brief. Type the sample input from the Input and output section and check the output against the four lines given there.

Read the comments in this program, because they show where each rule of the brief is enforced. The program is the reference solution in its plainest form. The hidden solution at the end adds a quick check that makes impossible words fast to reject, which is needed for the 100 percent level.

The output for the sample input is:

cafe YES 0 0
good NO
dog YES 2 0
fox NO

The output matches the four lines given in the brief. Run the program again on your own input before you move on. Change one letter of the grid, and predict whether the answer for each word changes. Then check your prediction.

Hints

Try each hint only when you are stuck, and try the step before you open the next hint.

Test list

Before you submit, run your program on each of these inputs and check the output by hand. Test C is the one most people get wrong.

Test A. The sample input from the Input and output section. Expected output is the four lines shown there.

Test B. A single cell:

1 1
a
1
a

Expected output: a YES 0 0.

Test C. A single row where a word would have to reuse a cell:

1 3
aba
2
aba
aa

Expected output: aba YES 0 0 and aa NO. The word aa needs two neighboring a cells. The two a cells are at columns 0 and 2, and they are not neighbors, because the b between them sits on the only path. So aa is not found.

Test D. A word longer than the grid. The grid is 2 by 2, which has 4 cells, and the word has 5 letters:

2 2
ab
cd
1
abcda

Expected output: abcda NO. The search must not crash when the word is longer than the grid. It should simply fail.

Test E. Two words that go in opposite directions, to check that both up and down are tried:

2 2
ab
cd
2
bd
ca

Expected output: bd YES 0 1 and ca YES 1 0. The word bd goes down from b at (0, 1) to d at (1, 1). The word ca starts at c in row 1, column 0, and goes up to a in row 0, column 0. No earlier cell in row-major order holds c, so the start is (1, 0).

Reference solution

The full solution is shown below. It is the Step 4 program with the quick rejection added. Read it after you have a version of your own, and compare the two line by line.

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
int R, C;
vector<string> grid;
vector<vector<bool>> seen;
const int dr[4] = {-1, 1, 0, 0};
const int dc[4] = {0, 0, -1, 1};
 
// True if the word can be spelled from cell (r, c) with word[k] at (r, c).
bool dfs(int r, int c, const string& word, int k) {
    if (grid[r][c] != word[k]) return false;
    if (k + 1 == (int)word.size()) return true;
    seen[r][c] = true;
    for (int d = 0; d < 4; d++) {
        int nr = r + dr[d], nc = c + dc[d];
        if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
        if (seen[nr][nc]) continue;
        if (dfs(nr, nc, word, k + 1)) {
            seen[r][c] = false;
            return true;
        }
    }
    seen[r][c] = false;
    return false;
}
 
// Quick check: does the grid contain this letter at all?
bool hasLetter(char ch) {
    for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++)
            if (grid[r][c] == ch) return true;
    return false;
}
 
int main() {
    cin >> R >> C;
    grid.resize(R);
    for (int i = 0; i < R; i++) cin >> grid[i];
    seen.assign(R, vector<bool>(C, false));
 
    int W;
    cin >> W;
    for (int w = 0; w < W; w++) {
        string word;
        cin >> word;
 
        // Reject impossible words before the search: too long, or a missing letter.
        bool possible = (int)word.size() <= R * C;
        for (char ch : word)
            if (!hasLetter(ch)) possible = false;
 
        bool found = false;
        int startR = -1, startC = -1;
        if (possible) {
            for (int r = 0; r < R && !found; r++) {
                for (int c = 0; c < C && !found; c++) {
                    if (dfs(r, c, word, 0)) {
                        found = true;
                        startR = r;
                        startC = c;
                    }
                }
            }
        }
        if (found) cout << word << " YES " << startR << " " << startC << "\n";
        else cout << word << " NO\n";
    }
    return 0;
}

Self-check before you submit

Read your code once, and answer these questions in your own words. If you cannot answer one, go back to the step it belongs to.

• Which line stops a path from reusing a cell, and where is the mark cleared?
• What is the base case of dfs, and why is the letter check before the length check?
• In what order are the start cells tried, and why does that order decide the output?
• What happens to the visited marks after a successful search?
• Why does NO appear only after the whole scan, and not inside the loop?

What this assignment covers

• Recursion with a base case that checks the last letter, and a recursive step over four neighbors.
• Backtracking: mark a cell, explore, and undo the mark on every return.
• Pruning: reject impossible words before the search, and stop the scan at the first match.
• Reading structured input in the right order, and printing exact output.
• Using the grid as a graph, where each cell is a node and each neighbor is an edge.