关于蟑螂随机漫步的编程问题，求思路～

Question

一直醉酒的蟑螂趴在15*15的方格纸的中央方格处，蟑螂一步迈出一个方格，该方格是此蟑螂所在方格周围8个方格中的任意一个，蟑螂无法进行任何思考，随即迈到8个方格的任意一个，求蟑螂何时迈出这张纸？

Answer 1

给你，已经编译运行确认了：#include<stdio.h>&nbsp;#include<stdlib.h>&nbsp;#include<time.h>&nbsp;//最大步数限制&nbsp;#define MAX_STEP_ON 65535&nbsp;#define MAX_X 15&nbsp;#define MAX_Y 15&nbsp;//房间的磁砖&nbsp;unsigned arr[MAX_X][MAX_Y];&nbsp;//相邻磁砖的位移&nbsp;const int stepx[]={-1,0,1,1,1,0,-1,-1};&nbsp;const int stepy[]={1,1,1,0,-1,-1,-1,0};&nbsp;//记录当前位置&nbsp;int current[2];&nbsp;//步数&nbsp;unsigned stepcount=0;&nbsp;int check(){&nbsp;int x,y;&nbsp;for(x=0;x<MAX_X;x++){&nbsp;for(y=0;y<MAX_Y;y++){&nbsp;if(arr[x][y]==0)&nbsp;return 0;&nbsp;}&nbsp;}&nbsp;return 1;&nbsp;}&nbsp;int printinfo(int success){&nbsp;if(!success){&nbsp;printf("It's not Complete walk around the room\n");&nbsp;}&nbsp;printf("the bug total walk:%d steps\n\n",stepcount);&nbsp;int x,y;&nbsp;for(x=0;x<MAX_X;x++){&nbsp;for(y=0;y<MAX_Y;y++){&nbsp;if(y==0)&nbsp;printf("\n%d\t",arr[x][y]);&nbsp;else&nbsp;printf("%d\t",arr[x][y]);&nbsp;}&nbsp;}&nbsp;return 1;}int clean(){&nbsp;int x=0,y=0;&nbsp;for(x;x<MAX_X;x++){&nbsp;for(y;y<MAX_Y;y++){&nbsp;arr[x][y]=0;&nbsp;}&nbsp;}&nbsp;printf("please input the begin Abscissa\n");&nbsp;scanf("%d",¤t[0]);&nbsp;printf("please input the begin Ordinate\n");&nbsp;scanf("%d",¤t[1]);&nbsp;arr[current[0]][current[1]]+=1;&nbsp;return 1;&nbsp;}&nbsp;int walk(){&nbsp;if(check()==0){&nbsp;int step=rand()%9;&nbsp;int nextx=current[0]+stepx[step];&nbsp;int nexty=current[1]+stepy[step];&nbsp;if(stepcount<MAX_STEP_ON){&nbsp;printinfo(0);&nbsp;exit(0);&nbsp;}&nbsp;if(nextx>=0&&nextx<=MAX_X-1&&nexty>=0&&nexty<=MAX_Y-1&&arr[nextx][nexty]<65535){&nbsp;++arr[nextx][nexty];&nbsp;++stepcount;&nbsp;//printf("%d,%d\t%d\n",current[0],current[1],step);&nbsp;current[0]=nextx;&nbsp;current[1]=nexty;&nbsp;}&nbsp;walk();&nbsp;}&nbsp;else{&nbsp;printinfo(1);&nbsp;exit(0);&nbsp;}&nbsp;return 1;}&nbsp;int main(){&nbsp;int isclean=clean();&nbsp;srand((unsigned)time(NULL));&nbsp;walk();&nbsp;}

Answer 2

我认为这是一个马可夫链问题。求状态转移矩阵收敛时从中心转移到外围的概率。