CS 141 - Lab 1

Word Search

Directions

Find a partner. Solve the following programming problem in C++. When you finish, turn it in electronically, one copy per team. When you are done, you should work on Homework 1 or Programming Assignment 1.

Overview

Given a grid of letters up to 50x50, find where in the grid a given word occurs. Each word is guaranteed to occur at least once. Matching may be done forward or backward, horizontally, vertically, or diagonally (8 cases total.)

Input Spec

Read in a single integer: this is the number of cases (grids) you will do on this run of the program. (1 int)

For each case, read in the number of lines (m) and the number of columns (n). (2 ints)

For each row, read in each character. (m repetitions of reading n characters).

Read in the number of words that will be found in the grid (w). (1 int)

Read in those words (w strings)

Continue with the next case.

Output Spec

Your output must match exactly the following, including whitespace.

For each word, print out the row and column of the starting letter in that word. In case there is more than one instance of that word in the grid, break ties first with lower row numbers, then with lower column numbers.

Testing

Test cases can be found here. Run these using regular UNIX redirection & testing:

./lab1 < inputFile | diff - outputFile

Where inputFile and outputFile will be one of these or a pair of your own creation.
lab1test1.in lab1test1.out
lab1test2.in lab1test2.out
If the testing line above produces no output when run with these tests, then you have completed the program.

Recommended Approach

There is no reason to use anything but normal >> stream extraction to get the input, since all input is from standard in. Use of getline will almost certainly give you great difficulty. Read the input spec, use the types recommended in ()'s. Input here should take no more than 30 minutes if you follow directions.
Write a function that will handle one case. Main should therefore be very small, just doing a little bit of input and calling that function in a loop.
Write a function that will find the coordinates for a word given the grid (vector<string> or an array of strings) and the word. Probably want to return a pair<int, int,> or pass the row and column results in by reference.
To write the above function, it is very nice to write
```
void find(vector<string> grid, string word, int& returnX,
int& returnY, int dx, int dy)
```
Where returnX and returnY are the return values, and dx and dy are the change in the x and y coordinate for each letter. Checking vertically down would be dx=0 and dy=1, horizontally backward would be dx=-1 and dy=0, and rising diagonally to the right would be dx=1 and dy=-1. This greatly reduces the amount of redundant code you have to write.
Check the boundaries of your string/vector/array accesses. Don't go off the ends of your arrays.
Ask your TA if you are stuck on anything for more than 5 minutes or so, especially if you didn't take a C++ course last quarter.
This can be done very easily in under 125 lines of readable code. If you get up to the 200 mark, stop and ask your TA what you are doing wrong.