搜索练习（地下城主，查找倍数）

地下城主

思路：这个其实就是bfs的板子，但是和以往的bfs不同，这个bfs适用于三维空间，也就是说多出一维需要进行搜索：

犯下的错误：在bfs的输出中我写成了cout<<q[tail].step+1<<endl;
由于在之前我就已经将step加过1了，所以输出这个tail所指向的队列还没有装入值（所以里面装的是脏数据），所以就会导致出错，应该是输出q[tail-1].step即可

收获到的东西：1.这毫无疑问是对我bfs的一次复习，bfs的具体步骤我都已经忘得差不多了 。
2.对于三维的方向数组我也有了了解，在之前二维图中方向数组是互补的，在三维数组中也是互补的。

代码如下：

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<cstdio>
#include<cstring>
#define Size 35
using namespace std;
char maze[Size][Size][Size];
bool vis[Size][Size][Size];
int dx[] = { 1,-1,0,0,0,0 };
int dy[] = { 0,0,1,-1,0,0 };
int dz[] = { 0,0,0,0,1,-1 };
int in_x, in_y, in_z;
int out_x, out_y, out_z;
int l, r, c;
typedef struct
{
	int x, y, z;
	int step;
}point;
void bfs()
{
	memset(vis, 0, sizeof(vis));
	int head = 1;
	int tail = 1;
	point q[Size * Size * Size];
	q[tail].x = in_x;
	q[tail].y = in_y;
	q[tail].z = in_z;
	q[tail].step = 0;
	vis[in_z][in_x][in_y] = true;
	tail++;
	while (head < tail)
	{
		for (int i = 0; i < 6; i++)
		{
			int tx = q[head].x + dx[i];
			int ty = q[head].y + dy[i];
			int tz = q[head].z + dz[i];
			if (vis[tz][tx][ty] || tz > l || tz<1 || tx>r || tx < 1 || ty<1 || ty>c)
				continue;
			if (maze[tz][tx][ty] != '#')
			{
				vis[tz][tx][ty] = true;
				q[tail].x = tx;
				q[tail].y = ty;
				q[tail].z = tz;
				q[tail].step = q[head].step + 1;
				tail++;
			}
			if (tx == out_x && ty == out_y && tz == out_z)
			{
				printf("Escaped in %d minute(s).\n", q[tail-1].step );
				return;
			}


		}
		head++;
	}
	cout << "Trapped!" << endl;
	return;
}
int main()
{
	while (true)
	{
		cin >> l >> r >> c;
		if (l == 0 && r == 0 && c == 0)
			return 0;
		for (int i = 1; i <= l; i++)
		{
			for (int j = 1; j <= r; j++)
			{
				for (int k = 1; k <= c; k++)
				{
					cin>>maze[i][j][k];
					if (maze[i][j][k] == 'S')
					{
						in_z = i;
						in_x = j;
						in_y = k;
					}
					if (maze[i][j][k] == 'E')
					{
						out_z = i;
						out_x = j;
						out_y = k;
					}
				}
			}
			getchar();
		}
		
		bfs();
	}
	return 0;
}

查找倍数

思路1bfs（时间会爆）：主要思路就是第一个插入队列的数是1，然后又两种情况第一后面直接乘以10，第二种情况就是乘以10之后然后再加1。这样就将只有两种1或0的i情况全部把包括进去了（只有取或者不取这两种情况）
思路2dfs：其实和第一种思路差不多，主要就是将插入改成了dfs中的递归，主要还是要考虑一种特殊情况：当递归深度为19的时候就需要停止递归，由于这个数最大不会超过100，而每次递归最少都会增加10倍，所以当我们递归到19的时候就需要停止递归了。

收获到的东西：在之前我都是只靠数组按位进行树的相加，现在我知道了可以通过队列或者递归进行树的相加（当然也与这题的特殊性有关，毕竟只有0和1）

代码如下：

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<string.h>
#include<queue>
using namespace std;
typedef long long ll;
int flag = 0;	
ll x;
void dfs(ll step,ll n)
{
	if(flag||step>=19)
	{
		return ;
	}
	if(n%x == 0)
	{
		cout << n <<endl;
		flag = 1;
		return ;
	}
	dfs(step+1,n*10);
	dfs(step+1,n*10+1);
}
int main()
{

	while(scanf("%lld",&x)!=EOF)
	{
		if(x == 0)
		{
			break;
		}
		flag = 0;
		dfs(0,1);
	}
	return 0;
}