/*
杀人狂魔汉尼拔博士逃狱了。通缉令发布后，大量军警出动并实施全天候追捕，不过狡猾的汉尼拔博士并没有落网。过了d日后，束手无策的警察们拜访了有着“编程天才”之称的查理教授。查理教授对汉尼拔博士留在监狱的笔记本进行分析后，做出了如下假设。
1）汉尼拔博士为了避开检查，只走山路；
2）汉尼拔博士越狱当天选择了与监狱相邻的村子之一作为藏身之处；
3）汉尼拔博士为了逃避追捕，每天往一个相邻的村子逃窜。
为了验证假设，教授找到了与监狱所在村子以山路连接的n个村子的地图。汉尼拔博士会按照此假设行动，而且会随机选择一个备选的村子。编写程序计算d日后汉尼拔博士在各个村子的概率。
*/
/*
1
5 2 0
0 1 1 1 0
1 0 0 0 1
1 0 0 0 1
1 0 0 0 0
0 1 1 0 0
3
0 2 4
*/

/*
2
5 2 0
0 1 1 1 0
1 0 0 0 1
1 0 0 0 0
1 0 0 0 0
0 1 0 0 0
3
0 2 4
8 2 3
0 1 1 1 0 0 0 0
1 0 0 1 0 0 0 0
1 0 0 1 0 0 0 0
1 1 1 0 1 1 0 0
0 0 0 1 0 0 1 1
0 0 0 1 0 0 0 1
0 0 0 0 1 0 0 0
0 0 0 0 1 1 0 0
4
3 1 2 6
*/

#include<stdio.h>
#include<stdlib.h> 
#include<time.h>  
#include<Windows.h>   
#include<graphics.h>
#include<conio.h>

const int NUM = 50;

struct map
{
	int link[NUM][NUM];//保存路线图的连通性
	int prison;//监狱地点
	int all;//村庄个数
	int s_num[NUM];//记录逃狱路径上村庄的标号
};

struct x_map//记录每一个村庄的位置坐标
{
	int x;
	int y;
};

IMAGE img1;
IMAGE img2;

int n = 0;

double jisuan(int end, int days, struct map* df, int near_1[NUM])//参数为：所要测试的村庄，逃狱的天数，map结构体指针，每一个村庄与其他村庄通路的数目
{
	if (days == 0)//递归出口，若第0天所在地为监狱则返回1，若不是则返回0
	{
		if (end == df->prison)
		{
			return (1);
		}
		else
			return (0);
	}

	double result = 0.0;

	for (int i = 0; i < df->all; ++i)//动态规划法分解子问题，并递归求解
	{
		double result1 = 0.0;
		if ((df->link[end][i]) == 1)//等于1则表示有通路
		{
			result1 = jisuan(i, days - 1, df, near_1);
			result = result + result1 / near_1[i];//不同的路径概率相加，求出总概率
		}
		if (result1)//记录线路，递归返回非零数则记录，否则跳过
		{
			df->s_num[n] = i;
			n++;
		}
	}
	return result;
}

void drawp(struct x_map df_1[], struct map* df, double res1, int end, int day)//图形化界面实现
{

	initgraph(1200, 800);
	loadimage(&img1, _T("./村庄图片.png"), 60, 60);
	loadimage(&img2, _T("./监狱.png"), 60, 60);
	loadimage(NULL, _T("./山林俯瞰图.jpg"), 1200, 800);

	for (int i = 0; i < df->all; i++)
	{
		if (i == df->prison)
		{
			putimage(df_1[i].x, df_1[i].y, &img2);
		}
		else
		{
			putimage(df_1[i].x, df_1[i].y, &img1);
		}
	}

	for (int i = 0; i < df->all; i++)
	{
		TCHAR s[5];
		_stprintf(s, _T("%d"), i);
		settextstyle(20, 16, _T("宋体"));
		outtextxy(df_1[i].x, df_1[i].y, s);
	}

	char buf[100] = {};
	char car[100] = {};

	sprintf(car, "逃狱第%d天疑犯在%d村的概率是", day, end);
	sprintf(buf, "%.8lf", res1);
	setlinestyle(PS_SOLID | PS_JOIN_BEVEL, 3);

	int j = 0;

	for (int i = 0; i < n; i++)//画路径
	{
		int x1, y1, x2, y2;
		x1 = df_1[df->s_num[i]].x;
		y1 = df_1[df->s_num[i]].y;
		if (i == n - 1 || df->s_num[i + 1] == df->prison)
		{
			x2 = df_1[end].x;
			y2 = df_1[end].y;
		}
		else
		{
			x2 = df_1[df->s_num[i + 1]].x;
			y2 = df_1[df->s_num[i + 1]].y;
		}
		if (df->s_num[i] == df->prison)
		{
			j++;
		}

		switch (j)
		{
		case 1:setlinecolor(RED); break;
		case 2:setlinecolor(BLUE); break;
		case 3:setlinecolor(BLACK); break;
		case 4:setlinecolor(YELLOW); break;
		case 5:setlinecolor(WHITE); break;
		}
		line(x1, y1, x2, y2);
	}

	if (MessageBoxA(NULL, buf, car, MB_OK) == IDOK)
	{
		closegraph();
	}
}

void setmap()//输入数据与建立村庄图表
{
	system("color F8"); //F是前景色代号，8是背景色代号
	printf("*************让我们一起寻找汉尼拔博士吧！！！***************\n");
	int num;
	printf("请输入测试用例个数：\n");
	scanf("%d", &num);
	while (num--)
	{
		struct x_map df1[20] = {};
		srand(time(NULL));
		int days;
		int near_1[NUM];//存储与第n个村庄相邻村子个数 
		struct map* df;
		df = (map*)malloc(sizeof(map));
		printf("请输入村庄的个数：\n");
		scanf("%d", &df->all);
		printf("请输入逃狱的天数：\n");
		scanf("%d", &days);
		printf("请输入监狱所在地：\n");
		scanf("%d", &df->prison);
		int i = 0;
		while (1)//分配村庄坐标
		{