题意很明了,搜索,有六种走法上,下,左,右,前,后。
只是该题需要加上剪枝。
N[A-1][B-1][C-1]==1或者A+B+C-3>T的时候直接输出-1即可。能节省400ms左右
题意:
从0,0,0走到A-1,B-1,C-1.6个走法。
分析:
最小步数,BFS。
这个不用优先队列还能节省一定的时间。
代码:
#include<stdio.h>
#include<queue>
#include<iostream>
#include<string.h>
#define judge if(y.a>=0&&y.a<A&&y.b>=0&&y.b<B&&y.c>=0&&y.c<C&&N[y.a][y.b][y.c]==0) {N[y.a][y.b][y.c]=1;Q.push(y);}//在这里修改状态,又错了很久!!!!
using namespace std;
bool N[52][52][52];
int A,B,C,T;
struct info
{
int a;
int b;
int c;
int t;
};
std::priority_queue<info> Q;
bool operator<(info x,info y)
{
return x.t>y.t;
}
int BFS(info x)
{
int i;
info y;
Q.push(x);
while(!Q.empty())
{
x=Q.top();Q.pop();
if(x.a==A-1&&x.b==B-1&&x.c==C-1) {while(!Q.empty()) Q.pop();return x.t;}
y.t=x.t+1;
y.a=x.a+1;y.b=x.b;y.c=x.c;
judge
y.a=x.a-1;y.b=x.b;y.c=x.c;
judge
y.a=x.a;y.b=x.b+1;y.c=x.c;
judge
y.a=x.a;y.b=x.b-1;y.c=x.c;
judge
y.a=x.a;y.b=x.b;y.c=x.c+1;
judge
y.a=x.a;y.b=x.b;y.c=x.c-1;
judge
}
return -1;
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
scanf("%d%d%d%d",&A,&B,&C,&T);
int i,j,k;
for(i=0;i<A;i++)
{
for(j=0;j<B;j++)
{
for(k=0;k<C;k++)
{
scanf("%d",&N[i][j][k]);
}
}
}
info X;
X.a=0;X.b=0;X.c=0;X.t=0;
if(N[A-1][B-1][C-1]==1||A+B+C-3>T) {printf("-1\n");}
else
{
int step=BFS(X);
if(step<=T) printf("%d\n",step);
else printf("-1\n");
}
}
return 0;
}
分享到:
相关推荐
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
leetcode中国 数据结构和算法编码 议程 ...1253 --- basic bfs 10. PKU 3126 --- bfs + complicate date deal 11. BNU 1054 --- basic bfs 12. LightOJ 1012 --- dfs transform 13. HDU 1495 --- compl
算法-数塔(HDU-2084).rar
算术(HDU-6715).rar
题意:有一位老师给N个学生分N个糖果,老师从第一个学生开始发糖果,老师所经过的学生至少要被分到一个糖果,求有多少种分法,比如这里有三个学生,老师有三个糖果,有四种分法:{3,0,0}, {2,1,0},{1,2,0},...
最短路(HDU-2544).rar
算法-确定比赛名次(HDU-1285).rar
算法-连连看(HDU-1175)(包含源程序).rar
算法-命运(HDU-2571)(包含源程序).rar
算法-欧拉回路(HDU-1878)(包含源程序).rar
算法-免费馅饼(HDU-1176)(包含源程序).rar
算法-六度分离(HDU-1869)(包含源程序).rar