# Demo entry 6786026

2017301500086

Submitted by anonymous on Mar 22, 2019 at 11:31
Language: C. Code size: 3.0 kB.

```#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define N 100
#define T 10000 //尝试次数

typedef struct Dog{
int posx;
int posy;
}Dog;

//狗随机选择方向自回避行走
int DogRun(int **p, int &length,int &Deadlength)
{
Dog dog;

int tag=1;//tag=1,成功走出；tag=0，陷入死胡同
dog.posx = N / 2;
dog.posy = N / 2;
p[dog.posx][dog.posy] = 1;

do
{
switch (rand() % 4) //每步有四个方向,随机选择的方向依次是上、右、下、左
{
case 0:
if (dog.posx <= 0 || dog.posx >= (N-1) || dog.posy <= 0 || dog.posy >= (N-1))//边界条件
return tag;
else if (p[dog.posx][dog.posy - 1] == 0)//判断是否能向上走
{
dog.posy--;//向上走
length++;
}
break;

case 1:
if (dog.posx <= 0 || dog.posx >= (N - 1) || dog.posy <= 0 || dog.posy >= (N - 1))
return tag;
else if (p[dog.posx + 1][dog.posy] == 0)//判断是否能向右走
{
dog.posx++;//向右走
length++;
}

break;

case 2:
if (dog.posx <= 0 || dog.posx >= (N - 1) || dog.posy <= 0 || dog.posy >= (N - 1))
return tag;
else	if (p[dog.posx][dog.posy + 1] == 0)//判断是否能向下走
{
dog.posy++;//向下走
length++;
}

break;
case 3:
if (dog.posx <= 0 || dog.posx >= (N - 1) || dog.posy <= 0 || dog.posy >= (N - 1))
return tag;
else if (p[dog.posx - 1][dog.posy] == 0)//判断是否能向左走
{
dog.posx--;//向左走
length++;
}

break;

default:
exit(1);
}

if (p[dog.posx][dog.posy - 1] == 1 && p[dog.posx + 1][dog.posy] == 1 && p[dog.posx][dog.posy + 1] == 1 && p[dog.posx - 1][dog.posy] == 1)//四个方向的值都为1，则陷入死胡同
{
tag = 0;
return tag;//返回是否陷入死胡同的标志
}

p[dog.posx][dog.posy] = 1;//将走过的位置赋值为1

} while (0 < dog.posx < (N -1)&& 0 < dog.posy < (N-1));//狗处于城市中

}

int main()
{
//创建一个N*N的二维数组
int **row;
srand(time(NULL));

row = (int**)malloc(sizeof(int*)*N);//分配N*N的空间
for (int i = 0; i < N; i++)
row[i] = (int*)malloc(sizeof(int)*N);

for (int i = 0; i < T; i++)
{
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
row[i][j] = 0;
length = 0;
AllLength += length;
}

printf("狗尝试的次数为：%d\n街道的数目为：%d", T, N);

AverageLength = (float)AllLength / T;
printf("\n%d次行走路径的平均长度为：%.3f", T,AverageLength);

AverageLength = (float)AllLength / T;