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;
			Deadlength = length;
			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;
	int DeadEndTime=0;//陷入死胡同次数
	int length = 0, AllLength = 0, DeadLength = 0,AllDeadLength=0;//每次尝试走的路径长度,T次总路径长度,每次走入死胡同的长度,所有走入死胡同的路径长度
	float AverageLength,AverageDeadLength;//平均路径
	float probability_DeadEnd;//走入死胡同概率
	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;
		if (!DogRun(row,length,DeadLength))
			DeadEndTime++;//陷入死胡同的次数	
		AllLength += length;
		AllDeadLength += DeadLength;
	}
	
	printf("狗尝试的次数为:%d\n街道的数目为:%d", T, N);

	probability_DeadEnd = (float)DeadEndTime / T;
	printf("\n陷入死胡同的概率为:%.3f", probability_DeadEnd);

	AverageLength = (float)AllLength / T;
	printf("\n%d次行走路径的平均长度为:%.3f", T,AverageLength);
	
	AverageLength = (float)AllLength / T;
	AverageDeadLength = (float)AllDeadLength / DeadEndTime;
	printf("\n%d次行走陷入死胡同的平均路径长度为:%.3f\n", T, AverageDeadLength);

	for (int i = 0; i < N; i++)//释放内存空间
		free(row[i]);
	free(row);

	system("PAUSE");
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).