題目出自DS課本第二章，滿有意思的一題。
題目
一隻喝醉酒的小強在地板上爬來爬去，
假設地板面積為row * col。
假設小強的起始位置為座標(i, j），
小強一次可以移動一格。
小強可以從他現在所待的格子，
移動到周遭其他格子，且機率相等。
請問小強爬過每塊面積至少一次，
需要花多久時間？
輸出總步數與每塊格子經過的次數。
分析
算是一題模擬題。
首先要知道地板的大小，
意即maxrow跟maxcol要定出來。
接著要知道起始點row, col。
從起始點開始往周遭移動，
我們還需要隨機函式與移動方式。
小強從自身待的格子移動到周遭至多有八格。
（八格就是八種情況）
需要考慮邊界問題，與上界問題。
邊界表示，小強移動只能在地板中，不能移動到地板之外；
上界表示，一個格子至多經過x次，超過x次就不能再進入格子。
（這個動作確保有解，程式才得以終止。）
課本提供一種很好的移動資料結構：利用陣列。
假設移動的row座標為mover，
移動的col座標為movec。
小強可以移動到左上，上，右上，右，右下，下，左下，左。
看出來了嗎！
一個點對應一組mover跟movec。
所以mover與movec的內容分別是：
mover[8] = {1, 1, 1, 0, -1, -1, -1, 0};
movec[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
至於要怎麼移動呢？
row = i + mover[j]
col = j + movec[j]
j從0到7為止。
如此配合隨機函式，可以隨機得到一個數字，
介於0到7，得到row與col後，再考慮邊界問題，
若在編界之內，且經過該格子的次數小於x就移動到(row, col)。
到小強每塊格子都經過至少一次時，
就可以輸出總步數與格子的經過情況數。
如果可以用顏色深淺代表移動次數那一定更好玩 XD。
實做程式碼
/* DS ch 2.9 exercise 9
* mythnc
* 2011/11/29 10:56:04
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ROW 40
#define COL 20
#define FALSE 0
#define TRUE 1
#define MAXT 50000
typedef struct point {
int x;
int y;
} Point;
void move(Point, int (*)[], int, int);
int terminal(int (*)[], int, int);
void printout(int (*)[], int, int);
int totalmove = 1;
int main(void)
{
int square[ROW][COL] = { 0 };
int maxrow, maxcol;
Point start;
printf("max row and col: ");
scanf("%d %d", &maxrow, &maxcol);
getchar();
printf("start point (x, y): ");
scanf("%d %d", &start.x, &start.y);
getchar();
move(start, square, maxrow, maxcol);
system("clear");
printout(square, maxrow, maxcol);
return 0;
}
/* move: cockroach move simulation */
void move(Point start, int (*s)[COL], int maxr, int maxc)
{
int xmove[] = {1, 1, 1, 0, -1, -1, -1, 0};
int ymove[] = {-1, 0, 1, 1, 1, 0, -1, -1};
int i, x, y;
srand((unsigned)time(NULL));
s[start.x][start.y]++;
while (!terminal(s, maxr, maxc)) {
system("clear");
printout(s, maxr, maxc);
getchar();
i = rand() % 8;
x = start.x + xmove[i];
y = start.y + ymove[i];
if (x >= 0 && x < maxr && y >= 0 && y < maxc
&& s[x][y] <= MAXT) {
s[x][y]++;
totalmove++;
start.x = x;
start.y = y;
}
}
}
/* terminal: terminal contidion */
int terminal(int (*s)[COL], int maxr, int maxc)
{
int i, j;
for (i = 0; i < maxr; i++)
for (j = 0; j < maxc; j++)
if (s[i][j] == 0)
return FALSE;
return TRUE;
}
/* printout: print out result */
void printout(int (*s)[COL], int maxr, int maxc)
{
int i, j;
printf("\ntotal move: %d\n", totalmove);
printf("count array:\n\n");
for (i = 0; i < maxr; i++) {
printf("%5d", s[i][0]);
for (j = 1; j < maxc; j++)
printf(" %5d", s[i][j]);
putchar('\n');
}
putchar('\n');
}
