There are a number of problems, known collectively as "random walk" problems which have been of long standing interest to the mathematical community. All but the most simple of these are extremely difficult to solve and for the most part they remain largely unsolved. One such problem may be stated as follows:

A (drunken) cockroach is placed on a given square in the middle of a tile floor in a rectangular room of size n x m tiles. The bug wanders (possibly in search of an aspirin) randomly from tile to tile throughout the room. Assuming that he/she may move from his/her present tile to any of the eight tiles surrounding him (unless he is against a wall) with equal probability, how long will it take him to touch every tile on the floor at least once?

Hard as this problem may be to solve by pure probability theory techniques, the answer is quite easy to solve using the computer. The technique for doing so is called "simulation" and is of wide-scale use in industry to predict traffic-flow, inventory control and so forth.

The problem may be simulated using the following method:

An array Room dimensioned N X M is used to represent the number of times our cockroach has reached each tile on the floor.

All the cells of this array are initialized to zero. The position of the bug on the floor is represented by the coordinates (xBUG,yBUG) and is initialized by random x and y positions such that x

Ex: int Room[6][7];

Let initial position of bug is 2,3 (dark shaded tile)

[0][0]	[0][1]	[0][2]	[0][3]	[0][4]	[0][5]	[0][6]
[1][0]	[1][1]	[1][2]	[1][3]	[1][4]	[1][5]	[1][6]
[2][0]	[2][1]	[2][2]	[2][3]	[2][4]	[2][5]	[2][6]
[3][0]	[3][1]	[3][2]	[3][3]	[3][4]	[3][5]	[3][6]
[4][0]	[4][1]	[4][2]	[4][3]	[4][4]	[4][5]	[4][6]
[5][0]	[5][1]	[5][2]	[5][3]	[5][4]	[5][5]	[5][6]

It is obvious that there are 8 possible moves (light shaded tiles) that the bug may randomly move to.

A random walk to one of the 8 given squares is simulated by generating a random value for K lying between 1 and 8. Of course the bug cannot move outside the room, so that coordinates which lead up a wall must be ignored and a new random combination formed. Each time a square is entered, the count for that square is incremented so that a non-zero entry shows the number of times the bug has landed on that square so far. When every square has been entered at least once, the experiment is complete.

Write a program to perform the specified simulation experiment. Your program MUST:

1) Handle values of N and M

• 2 < N 40
• 2 M <=20

2) Perform the experiment for

• N = 15, M = 15 starting point: (20,10)
• N = 39, M = 19 starting point: (1,1)

3) Have an iteration limit, that is, a maximum number of squares the bug may enter during the experiment. This assures that your program does not get "hung" in an "infinite" loop. A maximum of 50,000 is appropriate for this study.

4) For each experiment print:

a) the total number of legal moves which the cockroach makes;

b) the final Room array. This will show the "density" of the walk, that is the number of times each tile on the floor was touched during the experiment.

(Have an aspirin)