hdu 1253 bfs
2204 ワード
リンクacm.hdu.edu.cn/showproblem.php?pid=1253
G++タイムアウトでC++に変更して過ぎてしまい、最初は歩けなかったりゴールがもともと壁だったりすることを考えていなかったのですが、後で変更しました.
それから枝を切って、また他のものを直して、結局間違って、長い間考えてやっと歩けない情況がなくなったことに気づきました...
この迷路問題は,適合解を見つけたときに出力して終了し,タグを付け,メインプログラムでこのタグを表示し,なければ不適合を出力すべきであると感じた.これでは散らかりません.の
コード:
G++タイムアウトでC++に変更して過ぎてしまい、最初は歩けなかったりゴールがもともと壁だったりすることを考えていなかったのですが、後で変更しました.
それから枝を切って、また他のものを直して、結局間違って、長い間考えてやっと歩けない情況がなくなったことに気づきました...
この迷路問題は,適合解を見つけたときに出力して終了し,タグを付け,メインプログラムでこのタグを表示し,なければ不適合を出力すべきであると感じた.これでは散らかりません.の
コード:
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
int h,n,m,limit;
int d[6][3] = {1,0,0,-1,0,0,0,1,0,0,-1,0,0,0,1,0,0,-1};
int map[55][55][55];
bool visit[55][55][55];
int ok ;
struct state
{
int z,x,y;
int step;
}cur,next1;
void bfs(state temp)
{
queue<state> q;
temp.step = 0;
visit[temp.z][temp.x][temp.y] = true;
q.push(temp);
while(!q.empty())
{
cur = q.front();
if(cur.z == h-1 && cur.x == n-1 && cur.y == m-1)
{
if(cur.step <= limit)
{
printf("%d
",cur.step);
ok = 1; //
}
/*else // , -1 。。
{ // , Ok , 1
ok = 1; //
printf("-1
"); // 。。
}*/
return;
}
for(int i = 0;i < 6;i++)
{
next1.z = cur.z+d[i][0];
next1.x = cur.x+d[i][1];
next1.y = cur.y+d[i][2];
next1.step = cur.step+1;
if(next1.x>=0&&next1.x<n&&next1.y>=0&&next1.y<m&&next1.z>=0&&next1.z<h&&!visit[next1.z][next1.x][next1.y]&&map[next1.z][next1.x][next1.y]!=1)
{
q.push(next1);
visit[next1.z][next1.x][next1.y] = true;
}
}
q.pop();
}
}
int main ()
{
int t;
scanf("%d",&t);
while(t--)
{
ok = 0;
memset(visit,0,sizeof(visit));
scanf("%d %d %d %d",&h,&n,&m,&limit);
for(int i = 0;i < h;i++)
for(int j = 0;j < n;j++)
for(int k = 0;k < m;k++)
scanf("%d",&map[i][j][k]);
cur.z = 0;
cur.x = 0;
cur.y = 0;
if(h+n+m-3>limit||map[h-1][n-1][m-1]==1)
{
printf("-1
");
continue;
} // ,
bfs(cur);
if(!ok) printf("-1
"); // -1
}
return 0;
}