Suppose we have a 3x3 map. The map consists of numbers 1, 9 and 0. For example,
1 0 0
0 0 0
9 0 0
Now, start walking from the position of number 1 to 9. Note that we can only move toward four directions (Right, Down, Left, Up) and each position should be visited exact once. We want to know if we can reach the position of number 9 at the end.
As the previous example, number 9 can be reached because
1 4 5
2 3 6
9 8 7
Your program should print YES if number 9 can be reached, or NO otherwise.
hint:
1. You can open a 5x5 map, and place -1 on the boarder of the map to distinguish zeros and those -1.
2. You can try to travel the map random, the method is described as follows:
Start from number 1, choose one of the 4 directions at random. If this move is valid, then move to the new position and mark the position as 2.
Repeat this step (find the position that can be marked as 3, 4, …). If the chosen move is invalid, then pick another direction.
If the step was tried 10 times and failed (you cannot make a move after ten tries), then restore the map and start over again from number 1.
If you start over a million times and still cannot reach number 9 then print NO and exit the program.
The code rolling the dice is:
#include#include int main(void) { int i, x; for (i=0; i<100; i++) { x = rand()%6 + 1; printf("%3d", x); } return 0; }
A 3x3 map
YES / NO
Note that there is a newline character at the end of the string