小強歷險記

題目出自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');
}