Count words in a grid

[Stijn Verrept]

You have a grid like this:

Y Y F O U R
G F O U R G
F O U R Y G
G U R U O F
Y R Y R Y G

How many times does this grid have FOUR in it?

How should I make something that accepts a word and seeks in a Grid for
example? You can also go diagonal.

For example the F on (2, 0) can do FOUR horizontally, FOUR vertically,
BUT also:

F
O U R

or

F
O
U R

etc...

 

[Guest]

I think u can use "Deep First" search

 

[Greg Young]

Loop through all of the characters in the grid until you find a letter 1 ...
when you have found a letter 1 compare all of its neighbors to a letter 2
(repeat for the rest of the letters). Your termination point is when you
can't find the next letter.

consider ...

Y Y F O U R
G F O U R G
F O U R Y G
G U R U O F
Y R Y R Y G

I pass the two ys as they are not my first letter 'F' .. I get to the 3'rd
letter which is an F .. I begin comparing its neighbors.

-1,0 Y ... next
-1,-1 F ... next
0,-1 O ... thats my next letter recurse to search its neighbors (if you only
support straight lines i.e. diag vert etc this becomes much more efficient
as you only have a single recursive test but you wanted all so you have to
iterate through all of its neighbors)
..
..
..
..
eventually you find the word on 0,-1 ... you save the word and move to the
next neighbor from the first node .. +1,0 which is an F ... again recurse
its neighbors find O .. etc.

It is also important to NOT check the node that you came from .. this may
sound silly but consider the word mississippi

M I S S
X P J I
V P KM
Z I Q R

if you don't remember where you came from the algorithm will allow you to
reuse those letters when searchin neighbors as in the example above where
the iss gets reused.


Cheers,

Greg Young
MVP - C#
http://codebetter.com/blogs/gregyoung