李华

用户名：2645479600

访问量：18656

签　名：

等　　级
排　　名	478
经　　验	4691
参赛次数	2
文章发表	22
年　　龄	22
在职情况	学生
学　　校	华软、江理
专　　业	电信、计算机

　　自我简介：

欢迎探讨

TA的其他文章

蓝桥杯剪格子-题解(C语言代码)-----初学者可以看看，详细带图（dfs）
浏览：1127

[2013年第四届真题]危险系数-题解(C++代码)------STL，dfs
浏览：921

蓝桥杯历届试题-国王的烦恼-题解(C语言 with STL)---参考啊哈算法,文字解释详细
浏览：1572

你可能喜欢

蓝桥杯2015年第六届真题-机器人塔-题解(C语言代码)---常规深搜

　　作者: 李华　　　　发表时间：2020-03-30 23:54:32 浏览：499　|　评论：0　

原题链接：蓝桥杯2015年第六届真题-机器人塔

解题思路：
计算出最底层的人数是step_people个，然后从最底层往上深搜，每往上一层就将step_people减1。
###### 比如总共五层，最底下是5个，那么往上一层就是4个，以此类推，推到最后一层是1个，这层也放置完了，深搜就找到了一种情况。
```c
#include <stdio.h>
int a,b,step_people,high,sum;	//分别代表a,b，某一级的人数上限 ，总层级，用于计算总层级的sum 
int arr[1005],ans;
char tower[1005][1005];	//机器人塔 
char c[2]={'A','B'};
int check(int x,int y,char p)
{
	if(p=='A')	//如果准备下的位置是A
	{
		if((tower[x-1][y]=='A'&&tower[x-1][y+1]=='A')||(tower[x-1][y]=='B'&&tower[x-1][y+1]=='B'))
		return 1;
	}
	else	//如果准备下的位置是B 
	{
		if((tower[x-1][y]=='A'&&tower[x-1][y+1]=='B')||(tower[x-1][y]=='B'&&tower[x-1][y+1]=='A'))
		return 1;
	}
	return 0;
}
void dfs(int x,int y,int count_a,int count_b,int people,int now_max)	//深搜函数 
{
	if(x==high+1)	//如果搜到了最后一层，就得出了一种结果 
	{
		ans++;
		return;
	}
	if(x==1)	//如果在第一层 
	{
		if(count_a!=0||count_b!=0)	//如果人数没有用完 
		{
			if(y+1>now_max)	//如果再放一格这层铺满了
			{
				for(int i=0;i<2;i++)
				{
					if((i==0&&count_a>0)||(i==1&&count_b>0))	//如果a,b没有用完 
					{
						tower[x][y]=c[i];
						if(i==0)	count_a--;
						else		count_b--;
						dfs(x+1,1,count_a,count_b,people+1,now_max-1);
						if(i==0)	count_a++;	//回溯 
						else		count_b++;
					}
				}
			}
			else	//如果底这没有铺满 
			{
				for(int i=0;i<2;i++)
				{
					if((i==0&&count_a>0)||(i==1&&count_b>0))	//如果a,b没有用完 
					{
						tower[x][y]=c[i];
						if(i==0)	count_a--;
						else		count_b--;
						dfs(x,y+1,count_a,count_b,people+1,now_max);
						if(i==0)	count_a++;	//回溯 
						else		count_b++;
					}
				}
			}
		} 
	} 
	else	//如果不在第一层，就需要考虑脚下了 
	{
		if(count_a!=0||count_b!=0)	//如果人数没有用完 
		{
			if(y+1>now_max)	//如果再放一格这层铺满了
			{
				for(int i=0;i<2;i++)
				{
					if((i==0&&count_a>0)||(i==1&&count_b>0))	//如果a,b没有用完 
					{
						if(check(x,y,c[i]))	//如果准备下的格子符合才能放 
						{
							tower[x][y]=c[i];
							if(i==0)	count_a--;
							else		count_b--;
							dfs(x+1,1,count_a,count_b,people+1,now_max-1);
							if(i==0)	count_a++;	//回溯 
							else		count_b++;
						}
					}
				}
			}
			else	//如果这层没有铺满 
			{
				for(int i=0;i<2;i++)
				{
					if((i==0&&count_a>0)||(i==1&&count_b>0))	//如果a,b没有用完 
					{
						if(check(x,y,c[i]))	//如果准备下的格子符合才能放 
						{
							tower[x][y]=c[i];
							if(i==0)	count_a--;
							else		count_b--;
							dfs(x,y+1,count_a,count_b,people+1,now_max);
							if(i==0)	count_a++;	//回溯 
							else		count_b++;
						} 
					}
				}
			}
		} 	
	}
}
void arr_init()
{
	for(int i=0;i<1000;i++)	arr[i]=i;
} 
int main()
{
	scanf("%d %d",&a,&b);
	arr_init();
	for(int i=1;i<1000;i++)	//计算底层的人数和总层级 
	{
		sum+=i;
		if(sum==a+b)
		{
			step_people=i;	//最底层的人数就是此时的i 
			high=i;	//总层级也是当前的i 
			break;
		}
	}
	dfs(1,1,a,b,1,step_people);	//当前考虑（1,1）这个格子,a还剩a人，b还剩b人，当前第1层 ，当前层最大放step_people人 
	printf("%d",ans); 
	return 0;
}
```

0.0分

5 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

李华

TA的其他文章

你可能喜欢

不容易系列2 （C语言代码）

台球碰撞（C++代码）

C语言程序设计教程（第三版）课后习题8.8 （C++代码）

众数问题（C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

蓝桥杯2015年第六届真题-机器人塔-题解(C语言代码)---常规深搜

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

WU-格式化数据输出（C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

矩形面积交（C++代码）

剪刀石头布（C++代码）

C二级辅导-公约公倍（C语言代码）

C语言程序设计教程（第三版）课后习题12.3 （C语言代码）

李华

TA的其他文章

你可能喜欢

不容易系列2 （C语言代码）

台球碰撞 （C++代码）

C语言程序设计教程（第三版）课后习题8.8 （C++代码）

众数问题 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

蓝桥杯2015年第六届真题-机器人塔-题解(C语言代码)---常规深搜

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

WU-格式化数据输出 （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

矩形面积交 （C++代码）

剪刀石头布 （C++代码）

C二级辅导-公约公倍 （C语言代码）

C语言程序设计教程（第三版）课后习题12.3 （C语言代码）

台球碰撞（C++代码）

众数问题（C语言代码）

　　评论区

WU-格式化数据输出（C语言代码）

矩形面积交（C++代码）

剪刀石头布（C++代码）

C二级辅导-公约公倍（C语言代码）