[ALGO] Find the string in 2 dimensional matrix

Given a 2-dim matrix of characters 'm' and a string 's' - find if the string 's' is present in the matrix. Only characters in the neighboring cells of a cell can contribute to the string.

For example, for the case below B,D,F,G are neighbors of X. From 'X' possible strings (or substrings) are XB, XD, XF, XH.
|-----|-----|-----|
|  A  |  B  |  C  |
|-----|-----|-----|
|  H  |  X  |  D  |
|-----|-----|-----|
|  G  |  F  |  E  |
|-----|-----|-----|

Finally, an example. Given the matrix

(0,0)
    |-----|-----|-----|-----|
    |  y  |  a  |  a  |  o  |
    |-----|-----|-----|-----|
    |  a  |  o  |  a  |  o  |
    |-----|-----|-----|-----|
    |  y  |  a  |  o  |  o  |
    |-----|-----|-----|-----|
    |  h  |  a  |  a  |  o  |
    |-----|-----|-----|-----|
    |  y  |  a  |  h  |  o  |
    |-----|-----|-----|-----|
                            (3,3)

and asked to check for the string 'yahoo' the solution is true :
y - (3,0)
a - (3,1)
h - (3,2)
o - (3,3)
o - (2,3)

Walk the bridge, in pairs as fast a possible

There are 4 women who want to cross a bridge. They all begin on the same side. There is one flashlight. A maximum of two people can cross at one time. It is night. Any party who crosses, either 1 or 2 people, must have the flashlight with them. The flashlight must be walked back and forth, it cannot be thrown, etc. Each woman walks at a different speed. A pair must walk together at the rate of the slower woman's pace.
Woman 1: 1 minute to cross
Woman 2: 2 minutes to cross
Woman 3: 5 minutes to cross
Woman 4: 10 minutes to cross

For example if Woman 1 and Woman 4 walk across first, 10 minutes have elapsed when they get to the other side of the bridge. If Woman 4 then returns with the flashlight, a total of 20 minutes have passed and you have failed the mission.

Find jar with the contaminated pills

You have 4 jars of pills. Each pill is a certain weight, except for contaminated pills contained in one jar, where each pill is weight + 1. How could you tell which jar had the contaminated pills in just one measurement?

Source : http://www.sellsbrothers.com/fun/msiview/default.aspx?content=question.htm

Find the bulb for the switch

There is a room with a door (closed) and three light bulbs. Outside the room there are three switches, connected to the bulbs. You may manipulate the switches as you wish, but once you open the door you can't change them. Identify each switch with its bulb.

Source : My brother & http://www.sellsbrothers.com/fun/msiview/default.aspx?content=question.htm

Find direction of rotation

Imagine a disk spinning like a record player turn table. Half of the disk is black and the other is white. Assume you have an unlimited number of color sensors. How many sensors would you have to place around the disk to determine the direction the disk is spinning? Where would they be placed?

Source : http://www.sellsbrothers.com/fun/msiview/default.aspx?content=question.htm

Pay for 7 days using 1 7-segment gold bar and 2 cuts

You've got someone working for you for seven days and a gold bar to pay them. The gold bar is segmented into seven connected pieces. You must give them a piece of gold at the end of every day. If you are only allowed to make two breaks in the gold bar, how do you pay your worker?

Source : http://www.sellsbrothers.com/fun/msiview/default.aspx?content=question.htm