记得去年上概率论的时候最后一章讲述的是马尔科夫过程，当时只会做题。完全不知道这是干甚么。其实就是矩阵的遍历性问题。今天介绍的醉酒螳螂也是关于遍历性的问题。
1.问题叙述：
在矩形的房间里，铺有m * n块瓷砖，现将一只（醉酒的）螳螂放在地板中间一个指定的方格里，螳螂在房间中随机的从一块瓷砖漫步到另一块瓷砖（可能是在找一块奶酪，呵呵）。假设它可能从其他所在的瓷砖移动到其周围八块瓷砖中的任何一块（除非碰到墙壁），那么它至少接触每块瓷砖一次，将花费多少时间？
2. 强调：
这个算法有什么用？使用计算机解决此问题的技术称为模拟，这种技术广泛应用于工业中，用来预测运输流量，存货控制等问题。
3.解决思路：
用一个m * n数组作为计数器来表示螳螂到达每一块瓷砖的次数，每个数组单元的初始化值均为0，螳螂在地板的位置用坐标表示（x， y）（可以直接用整型值，也可以用结构体，二者随意），则螳螂的八种可能移动用（x + xmove[choose], y + ymove[choose]）的瓷砖表示,其中0 <= choose <= 7, 并且：
xmove[0] = -1 ymove[0] = 1
xmove[1] = 0 ymove[1] = 1
xmove[2] = 1 ymove[2] = 1
xmove[3] = 1 ymove[3] = 0
xmove[4] = 1 ymove[4] = -1
xmove[5] = 0 ymove[5] = -1
xmove[6] = -1 ymove[6] = -1
xmove[7] = -1 ymove[7] = 0
螳螂向其相邻的八个方格的随机漫步通过产生一个随机数choose来模拟，而且，螳螂不能爬出房间，螳螂每进入一次方格，该方格计数器加1，当所有的方格全部为非零时，说明螳螂已经遍历完整个矩阵，是不是和马尔科夫过程非常像的。。。。
4.代码如下：
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
//总共移动的最多次数
#define MAX5000
//房间的长和宽
#define X10
#define Y10
#define NOTEND-1
int matrix[X][Y];
int judgeMatrixEnd(void);//判断矩阵是否每个方格进入一次
void showMatrix(void);//显示矩阵
void showMatrix(void)
{
int i, j;
for(i = 0; i < X; i ++)
{
for(j = 0; j < Y; j++)
printf("%3d", matrix[i][j]);
printf("\n");
}
}
int judgeMatrixEnd(void)
{
int i, j;
for(i = 0; i < X; i++)
for(j = 0; j < Y; j++)
{
if(matrix[i][j] <= 0)
return NOTEND;//没有结束
}
return END;//结束
}
int main(void)
{
int x, y;
int moveCount = 0;//移动次数
clock_t start = 0, end = 0;//移动起始和终止时间
double moveTime;//移动时间
int choose;//选择的方向
int lastx, lasty;//最后一次合理的坐标
//下面的两个数组成对出现代表着随机点对应的八个方向
int xmove[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int ymove[8] = {1, 1, 1, 0, -1, -1, -1, 0};
/* 右 右 右 下 左 左 左 上
上 边 下 边 下 边 上 边
*/
memset(matrix, 0, sizeof(matrix));//把矩阵初始化为0
x = rand() % X;//随机定位横坐标
y = rand() % Y;//随机定位纵坐标
matrix[x][y]++;//随机定位的次数加1
showMatrix();
//当某个位置出现的次数超过最大次数或者每个方格至少进入一次时，实验结束
while(moveCount < MAX && judgeMatrixEnd() == NOTEND)
{
choose = rand() % 8;
//蟑螂的移动位置不能超过四个边界
if(x + xmove[choose] >= 0 && y + ymove[choose] >= 0
&& x + xmove[choose] < X && y + ymove[choose] < Y)
{
//改变蟑螂的位置
x += xmove[choose];
y += ymove[choose];
matrix[x][y]++;//该位置次数加1
//保存当前坐标
lastx = x;
lasty = y;
}
else
{
//如果不合理则返回到上一次位置
x = lastx;
y = lasty;
continue;
}
system("CLS");
showMatrix();
moveCount++;
}
end = clock();
moveTime = (double)(end - start) / CLK_TCK;
printf("\n移动的次数为:%d", moveCount);
printf("\n所花费的时间为：%lf", moveTime);
getch();
return 0;
}
