I - 승리 대도 망 (BFS)

Ignatius 가 마왕 에 게 잡 혀 갔 어 요. 어느 날 마왕 이 출장 을 갔 어 요. Ignatius 가 도망 갈 수 있 는 좋 은 기회 예요. 마왕 은 한 성에 살 았 어 요. 성 은 A * B * C 의 입방체 로 A 개 B * C 의 행렬 로 표 시 될 수 있어 요. 처음에 Ignatius 는 (0, 0, 0) 의 위치 에 갇 혔 어 요. 성 보 를 떠 난 문 은 (A - 1, B - 1, C - 1) 의 위치 에 있어 요. 마왕 이 T 분 후에 성 으로 돌아 갈 거 라 는 걸 알았어 요.Ignatius 는 매 분 마다 한 좌표 에서 인접 한 여섯 개의 좌표 중 하나 로 이동 할 수 있 습 니 다. 지금 성 지 도 를 드 립 니 다. Ignatius 가 마왕 이 돌아 오기 전에 성 을 떠 날 수 있 는 지 계산 해 보 세 요.
 
Input
데 이 터 를 입력 하 는 첫 번 째 줄 은 정수 K 로 테스트 데이터 의 수량 을 나타 낸다. 각 조 의 테스트 데이터 의 첫 번 째 줄 은 네 개의 정수 A, B, C 와 T (1 < = A, B, C < = 50, 1 < = T < = 1000) 로 각각 성의 크기 와 마왕 이 돌아 오 는 시간 을 나타 낸다. 그 다음 에 A 개의 입력 데이터 (먼저 0 번 째, 그 다음 에 1 번 째, 2 번 째...) 이 고 각 입력 데 이 터 는 B 줄 이 있 으 며 각 줄 에는 C 개의 정수 가 있다.미로 의 구 조 를 대표 합 니 다. 그 중에서 0 은 길 을 대표 하고 1 은 벽 을 대표 합 니 다. (입력 설명 이 명확 하지 않 으 면 Sample Input 의 미로 설명 을 참고 하 십시오. 위의 그림 의 미 로 를 표시 합 니 다) 특히 주의 하 십시오. 이 문제 의 테스트 데이터 가 매우 큽 니 다. scanf 입력 을 사용 하 십시오. cin 을 사용 하면 시간 을 초과 하지 않 을 수 있 습 니 다. 본 OJ 에 서 는 Visual C + + 를 사용 하여 제출 하 십시오.
Output
각 조 의 테스트 데이터 에 대해 Ignatius 가 마왕 이 돌아 오기 전에 성 을 떠 날 수 있다 면 최소 몇 분 이 걸 리 는 지 출력 하 십시오. 그렇지 않 으 면 출력 - 1.
Sample Input

1
3 3 4 20
0 1 1 1
0 0 1 1
0 1 1 1
1 1 1 1
1 0 0 1
0 1 1 1
0 0 0 0
0 1 1 0
0 1 1 0

Sample Output

11

사고: 전형 적 인 광 검색 문 제 는 차단 으로 인해 영원히 문 앞 에 도착 하지 못 하 는 상황 에 주의 하고 특 판 해 야 한다.

#include
#include
#include
using namespace std;
const int N = 55;
struct node{
	int x,y,z;
	int step;
	node(){
	}
	node(int xx,int yy,int zz,int ss){
		x=xx;
		y=yy;
		z=zz;
		step=ss;
	}
};
int mp[N][N][N];
int vis[N][N][N];
int a,b,c,t;
int nex[6][3]={1,0,0,-1,0,0,0,1,0,0,-1,0,0,0,1,0,0,-1};
bool judge(int x,int y,int z){
	if(x<0||y<0||z<0) return 1;
	if(x==a||y==b||z==c) return 1;
	if(vis[x][y][z]||mp[x][y][z]) return 1;
	return 0;
}
int BFS(int sx,int sy,int sz){
	queuep;
	p.push(node(sx,sy,sz,0));
	vis[sx][sy][sz]=1;
	int flag=0;
	while(!p.empty()){
		node temp=p.front();
		p.pop();
		if(temp.x==a-1&&temp.y==b-1&&temp.z==c-1){
			flag=1;
			return temp.step;	
		}
		for(int i=0;i<6;i++){
			int tx=temp.x+nex[i][0];
			int ty=temp.y+nex[i][1];
			int tz=temp.z+nex[i][2];
//			printf("(%d,%d,%d)-->(%d,%d,%d)
",temp.x,temp.y,temp.z,tx,ty,tz);
			if(judge(tx,ty,tz)) continue;
			
			//printf("(%d,%d,%d)
",tx,ty,tz);
			
			vis[tx][ty][tz]=1;
			p.push(node(tx,ty,tz,temp.step+1));
		}
	}
	if(!flag) return 100000;
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		memset(vis,0,sizeof(vis));
		scanf("%d%d%d%d",&a,&b,&c,&t);
		for(int i=0;it) ans=-1;
printf("%d",ans);
}
return 0;
}