首页 LMVE论坛 资讯 插画 时光机 我的社区 用户 搜索

[C/C++](递归算法)用C写一个解《微信小程序-一笔画完》的脚本

无闻风
发表于 2019-06-27 14:39:27
0
201

不知道咋玩的自己去研究一下下

建一个c控制台程序

// ConsoleApplication1.cpp: 定义控制台应用程序的入口点。
#include "stdafx.h"
int num, map_x = 7, map_y = 9, map_mod, move, old_move;
int player_x=4, player_y=5;
int hc_x[1000];//路径缓存
int hc_y[1000];
int jd_num = 0;//节点数量
int dj_num = 0;//节点数量
char map[10][10];
char overdis[10][10];
int over;
int allconst =0;
char debug_map[20][20] =
{
	{ 0,0,0,0,0,0,0,0,0 },
	{ 0,0,1,1,0,0,1,1,0 },
	{ 0,1,1,1,1,1,1,1,0 },
	{ 0,1,1,0,1,1,0,1,0 },
	{ 0,1,1,1,1,1,1,1,0 },
	{ 0,1,0,1,2,0,1,1,0 },
	{ 0,1,1,1,1,1,1,1,0 },
	{ 0,0,0,1,1,0,0,1,0 },
	{ 0,1,1,1,1,1,1,1,0 },
	{ 0,0,1,1,1,1,1,1,0 },
	{ 0,0,0,0,0,0,0,0,0 }
};
#define entity "[ ]"
#define hole   "   "
#define player " * "
int disover();
/*******************/
int checkwin()//检查是否胜利
{
	char i = 0, j = 0, x, y;
	x = map_x;
	y = map_y;
	for (i = 1; i <= y; i++)
	{
		for (j = 1; j <= x; j++)
		{
			if (map[j][i] == 1)
			{
				return 1;
			}
		}
	}
	return 0;
}

int displaymapandplayer(char a)//显示地图和玩家
{
	char i = 0, j = 0, x, y;
	x = map_x;
	y = map_y;
	for (i = 1; i <= y; i++)
	{
		for (j = 1; j <= x; j++)
		{
			if (player_x == j&player_y == i)
			{
				if (a == 1)
				{
					printf(player);
				}
				map[j][i] = 0;
			}
			else
			{
				if (map[j][i] == 1)
				{
					if (a == 1)
					{
						printf(entity);
					}
				}
				if (map[j][i] == 0)
				{
					if (a == 1)
					{
						printf(hole);
					}
				}
			}
		}
		if (a == 1)
		{
			printf(" ");
		}
	}
	return 0;
}

int moveplayer(int a, int b)//移动玩家 a移动方向  b是否移动 。如果b==0只会返回这一步是否可以走,不会真的移动玩家
{
	if (a == 8)
	{
		if (map[player_x][player_y - 1] == 0)
		{
			return 0;
		}
		else
		{
			if (b == 1)
			{
				player_y = player_y - 1;
			}
			return 1;
		}
	}
	if (a == 2)
	{
		if (map[player_x][player_y + 1] == 0)
		{
			return 0;
		}
		else
		{
			if (b == 1)
			{
				player_y = player_y + 1;
			}
			return 1;
		}
	}
	if (a == 4)
	{
		if (map[player_x - 1][player_y] == 0)
		{
			return 0;
		}
		else
		{
			if (b == 1)
			{
				player_x = player_x - 1;
			}
			return 1;
		}
	}
	if (a == 6)
	{
		if (map[player_x + 1][player_y] == 0)
		{
			return 0;
		}
		else
		{
			if (b == 1)
			{
				player_x = player_x + 1;
			}
			return 1;
		}
	}



}

/*************************************************************************/
int countrun(char hl)//计算可以走的方向
{
	char a = 0;
	if (hl == 0)
	{
		if (moveplayer(8, 0))
		{
			a = 1;
		}
	}
	if (hl == 1)
	{
		if (moveplayer(2, 0))
		{
			a = 1;
		}
	}
	if (hl == 2)
	{
		if (moveplayer(4, 0))
		{
			a = 1;
		}
	}
	if (hl == 3)
	{
		if (moveplayer(6, 0))
		{
			a = 1;
		}
	}
	return a;
}

int mainrecursive()//递归
{
	char a = 0, b;
	for (a = 0; a < 4; a++)
	{
		if (countrun(a))
		{
			if (a == 0)
			{
				old_move = 8;
				moveplayer(8, 1);
				hc_x[jd_num] = player_x;
				hc_y[jd_num] = player_y;
			}
			else
			{
				if (a == 1)
				{
					old_move = 2;
					moveplayer(2,1);
					hc_x[jd_num] = player_x;
					hc_y[jd_num] = player_y;
				}
				else
				{
					if (a == 2)
					{
						old_move = 4;
						moveplayer(4, 1);
						hc_x[jd_num] = player_x;
						hc_y[jd_num] = player_y;
					}
					else
					{
						if (a == 3)
						{
							old_move = 6;
							moveplayer(6, 1);
							hc_x[jd_num] = player_x;
							hc_y[jd_num] = player_y;
						}
					}
				}
			}
			//dj_num = jd_num;
			jd_num += 1;
			displaymapandplayer(0);//是否打印过程(函数必须存在)
			//disover();
			//printf("输入任意字符继续 ");
			//scanf_s("%d", &over);
			mainrecursive();
		}
	}
	if (!checkwin())
	{
		return 1;
	}
	else
	{
		//jd_num = dj_num;
		jd_num -= 1;
		map[player_x][player_y] = 1;//回溯 地图还原
		player_x = hc_x[jd_num-1];  //玩家返回上一次的位置
		player_y = hc_y[jd_num-1];
	}
	return 0;
}

int disover()
{
	int a;
	char i = 0, j = 0, x, y;
	x = map_x;
	y = map_y;
	printf("解法:");
	printf("%d ", allconst);
	for (a = 0; a < jd_num; a++)
	{
		overdis[hc_x[a]][hc_y[a]] = a;
		//printf("%d", hc_x[a]);
		//printf(":");
		//printf("%d", hc_y[a]);
		//printf(" ");
	}
	for (i = 1; i <= y; i++)
	{
	for (j = 1; j <= x; j++)
	{
	if (overdis[j][i])
	{
            printf("[");
	    printf("%2d", overdis[j][i]);
	    printf("]");
	}
	else
	{
            printf("    ");
	}
	}

	printf(" ");

	}
	printf(" ");
	return 0;

}
void allmainrecursive()//递归
{
	char a = 0, b;
	for (a = 0; a < 4; a++)
	{
		if (countrun(a))
		{
			if (a == 0)
			{
				//old_move = 8;
				moveplayer(8, 1);
				hc_x[jd_num] = player_x;
				hc_y[jd_num] = player_y;
			}
			else
			{
				if (a == 1)
				{
					//old_move = 2;
					moveplayer(2, 1);
					hc_x[jd_num] = player_x;
					hc_y[jd_num] = player_y;
				}
				else
				{
					if (a == 2)
					{
						//old_move = 4;
						moveplayer(4, 1);
						hc_x[jd_num] = player_x;
						hc_y[jd_num] = player_y;
					}
					else
					{
						if (a == 3)
						{
							//old_move = 6;
							moveplayer(6, 1);
							hc_x[jd_num] = player_x;
							hc_y[jd_num] = player_y;
						}
					}
				}
			}
			//dj_num = jd_num;
			jd_num += 1;
			displaymapandplayer(0);//是否打印过程(函数必须存在)
								   //disover();
								   //printf("输入任意字符继续 ");
								   //scanf_s("%d", &over);
			allmainrecursive();
		}
	}
	if (!checkwin())
	{
		allconst += 1;
		disover();
	}
                //jd_num = dj_num;
		jd_num -= 1;
		map[player_x][player_y] = 1;//回溯 地图还原
		player_x = hc_x[jd_num-1];  //玩家返回上一次的位置
		player_y = hc_y[jd_num-1];
}
int main()
{
RGO:
	char i = 0, j = 0;
	jd_num = 0;//节点数量
	dj_num = 0;//节点数量
	allconst = 0;
	do
	{
		printf("输入布局模式: ");
		printf("0:输入布局 ");
		printf("1:自带布局 ");
		scanf_s("%d", &map_mod);
	} while ((map_mod != 1)&(map_mod != 0));
	if (map_mod == 0)
	{
		printf("布局输入方式: ");
		printf(" x--------------> ");
		printf("y nnnnnnnnnnnnnn ");
		printf("| nnnnnnnnnnnnnn ");
		printf("| nnnnnnnnnnnnnn ");
		printf("| nnnnnnnnnnnnnn ");
		printf("| nnnnnnnnnnnnnn ");
		printf("| nnnnnnnnnnnnnn ");
		printf("v                ");
		printf(" ");
		do
		{
			printf("输入地图长度:X(1-9) ");
			scanf_s("%d", &map_x);
		} while (map_x<1 | map_x>9);
		do
		{
			printf("输入地图宽度:Y(1-9) ");
			scanf_s("%d", &map_y);
		} while (map_y<1 | map_y>9);
		printf("输入地图布局:(输入内容0|1,从左到右,从上到下) ");
		for (i = 1; i <= map_y; i++)
		{
			for (j = 1; j <= map_x; j++)
			{
				do
				{
					printf("%d,%d:", j, i);
					scanf_s("%d", &map[j][i]);
				} while ((map[j][i] != 1)&(map[j][i] != 0));
				printf("%d ", map[j][i]);
			}
		}
		do
		{
			printf("输入玩家X轴:(1-9) ");
			scanf_s("%d", &player_x);
		} while (map_x<1 | map_x>9);
		do
		{
			printf("输入玩家Y轴:(1-9) ");
			scanf_s("%d", &player_y);
		} while (map_y<1 | map_y>9);
		printf(" ");
		displaymapandplayer(1);
	}
	if (map_mod == 1)
	{
		for (i = 1; i <= map_y; i++)
		{
			for (j = 1; j <= map_x; j++)
			{
				//printf("%d,%d:", j, i);
				//printf("%d ", debug_map[i][j]);
				map[j][i] = debug_map[i][j];
			}
		}
		//printf(" ");
		displaymapandplayer(1);
	}
	hc_x[jd_num] = player_x;
	hc_y[jd_num] = player_y;
	jd_num += 1;
	printf(" ");
	do
	{
		printf("0:玩家模式 ");
		printf("1:归递方法求解 ");
		printf("2:非归递方法求解 ");
		printf("3:计算所有解 ");
		scanf_s("%d", &num);
	} while (num<0 | num>3);
	if (num == 0)
	{
		while (checkwin())
		{
			do
			{
				printf("输入移动方向: ");
				printf("8:上 ");
				printf("2:下 ");
				printf("4:左 ");
				printf("6:右 ");
				scanf_s("%d", &move);
			} while ((move != 8)&(move != 2)&(move != 4)&(move != 6));
			moveplayer(move, 1);
			displaymapandplayer(1);
		}
        	printf("YOU WIN! ");
	}
	if (num == 1)
	{
		if (mainrecursive())
		{
			allconst += 1;
			printf("计算完成! ");
			disover();
		}
		else
		{
			printf("无解! ");

		}
	}
	if (num == 3)
	{
			allmainrecursive();	
			printf("计算完成! ");	
	}
	printf("0:结束 ");
	printf("1:再来一次 ");
	scanf_s("%d", &over);
	if (over == 1)
	{
		goto RGO;
	}
	return 0;
}

最后修改 2019-06-27 14:39:27
0
201
用户评论
一起折腾