|
楼主 |
发表于 2018-2-13 18:24:39
|
显示全部楼层
这里的时间,其实就是使用BFS的解答树的深度。
广度优先搜索,即在遍历解答树时使每次状态转移时扩展出尽可能多的新状态,并按照各个状态出现的先后顺序依次拓展他们(需要队列)。BFS的扩展往往呈幂级数kuo增长,当BFS的扩展深度扩大到一定程度,其扩展即使对于计算机也是一堆庞大的数据。因此,需要采取相应的措施来制约这种无限扩展。这个措施就是剪枝。
剪枝,即剪掉解答树上不可能存在我们所需答案的子树。这里就不多分析了。本题所要剪掉的是后出现的到达(x,y,z)的状态,相对于最先出现的(x,y,z)的状态而言,前者的深度不可能小于后者。因此,前者就没有必要继续扩展。
- #include<cstdio>
- #include<queue>
- #define maxn 50
- using namespace std;
- bool mark[maxn][maxn][maxn];
- int maze[maxn][maxn][maxn];
- struct N
- {
- int x,y,z;
- int t;
- };
- queue<N> Q;
- int go[][3]=
- {
- 1,0,0,
- -1,0,0,
- 0,1,0,
- 0,-1,0,
- 0,0,1,
- 0,0,-1
- }; //坐标变换数组
- int BFS(int a,int b,int c)
- {
- while(!Q.empty())
- {
- N now=Q.front();
- Q.pop();
- for(int i=0;i<6;i++)
- {
- int nx=now.x+go[i][0];
- int ny=now.y+go[i][1];
- int nz=now.z+go[i][2];
- if(nx<0||nx>=a||ny<0||ny>=b||nz<0||nz>=c)
- continue;
- if(maze[nx][ny][nz]==1)
- continue;
- if(mark[nx][ny][nz]==true)
- continue;
- N tmp;
- tmp.x=nx;
- tmp.y=ny;
- tmp.z=nz;
- tmp.t=now.t+1;
- Q.push(tmp);
- mark[nx][ny][nz]==true;
- if(nx==a-1&&ny==b-1&&nz==c-1)
- return tmp.t;
- }
- }
- return -1;
- }
- int main()
- {
- int T;
- scanf("%d",&T);
- while(T--)
- {
- int a,b,c,t;
- scanf("%d%d%d%d",&a,&b,&c,&t);
- for(int i=0;i<a;i++)
- for(int j=0;j<b;j++)
- for(int k=0;k<c;k++)
- {
- scanf("%d",&maze[i][j][k]);
- mark[i][j][k]=false;
- }
- while(!Q.empty()) Q.pop();
- mark[0][0][0]=true;
- N tmp;
- tmp.t=tmp.x=tmp.y=tmp.z=0;
- Q.push(tmp);
- int rec=BFS(a,b,c);
- if(rec>=0&&rec<=t)
- printf("%d\n",rec);
- else
- printf("-1\n");
- }
- return 0;
- }
复制代码 |
|