how many rats can run out of rat maze?

Recently, I took a linux c test, it is really a mess experience. My computer was broken during the windows-linux OS switching. That''s not the worst, one of the test item caught my eyes, I focus on it and enjoyed myself, I lost the time and lost the test.

But anything did I get? At last I reached the new understanding to the path finding, actually, I connected the bit storage, list array tree,sub-string search into the topological abstraction. Let me give the question below, I think most of you maybe have do such question many times, but for me, It is my first time.

/* Question 4: Maze Problem
* Starting point is m[0][0], need to find a path go to m[9][9]. 0
means OK,
* 1 means cannot go there, boundary is 0 and 9, cannot go beyond
boundary.
* Each step can be made horizontally or vertically for one more grid
(diagonal
* jump is not allowed).
* Your program should print a series of grid coordinates that start
from m[0][0]
* and go to m[9][9]
* Hint: No need to find the shortest path, only need to find one path
that gets
* you to destination.
*/

int matrix[10][10] =
{ 0, 1, 1, 0, 1, 1, 1, 1, 0, 1,
0, 1, 0, 0, 0, 0, 1, 1, 1, 1,
0, 1, 0, 0, 1, 0, 1, 1, 1, 1,
0, 0, 0, 1, 1, 0, 1, 1, 1, 1,
0, 1, 1, 1, 0, 0, 0, 0, 0, 1,
1, 1, 1, 1, 0, 1, 1, 0, 0, 1,
1, 1, 0, 1, 0, 0, 0, 0, 0, 1,
0, 1, 0, 0, 1, 1, 1, 1, 0, 1,
0, 1, 1, 0, 1, 1, 1, 1, 0, 1,
0, 1, 1, 1, 1, 1, 1, 1, 0, 0
};

and its general version is
Lets assume we have a rat maze as represented by the following NxM matrix
where S is the start location and F is the end location.

S 0 0 0 0 0
1 1 0 0 0 0
1 0 1 0 0 0
1 0 1 0 0 0
0 1 0 1 0 0
1 0 0 0 1 0
0 1 1 1 1 F

The idea (as with any rat maze) is to traverse from S to F. The matrix can
have only 0 and 1 as values. 1 represents a path that can be taken and 0
represents a blocked path.

We can make the following assumption:
S will always be (0,0) and F will always be (N,M).

As seen from above, there can be many paths from S to F.

How do we find the shortest (or longest) path from S to F without actually
traversing all the possible paths.

During the software design, I found it is not only a IQ game, lots of practical technologies from it. I list some interesting directions maybe related to it:
1. network topological info management
2. search engine
3. OS kernel for process and task management
4. graphic data processing
5. DNA data segment analysis
6. video compression
7. AI

Besides the recursion algorithm.
The basic solution to such problem is
1. build the elements of the specific area,
2. mapping them into 0,1 bit array,design the list structure to store the useful info in the specific area,
3. finding the topological of these lists to optimize the elements organization.
4. give solution from the topological structure.

Is it interesting, Would you like to have a try to write a program of it? Maybe you can finding other application area for such a basic problem. If you interested it, kindly send email to me jack.yan@ieee.org, I will send you some initial source code written by me.
I want to know how many people are interested in such programming. If more, let''s breeze it as a child, our rat maze child.

Replies: