Untitled

mail@pastecode.io avatar
unknown
plain_text
2 months ago
2.2 kB
3
Indexable
Never
#include <iostream>
using namespace std;

int T, N, map[35][35][35], buoc[35][35][35], mindem, strx, stry, strz;
bool visit[35][35][35];
int front, rear;
int const maxS =  10000000;
int qx[maxS], qy[maxS], qz[maxS];
int dx[6]={ 0, 0, 0, 0,-1, 1};
int dy[6]={ 0, 0,-1, 1, 0, 0};
int dz[6]={-1, 1, 0, 0, 0, 0};

bool check(int x, int y, int z){
	return x>=1&&x<=N&&y>=1&&y<=N&&z>=1&&z<=N;
}
void POP(){
	if(front==maxS-1) front=-1;
	front++;
}
void PUSH(int x, int y, int z){
	if(rear==maxS-1) rear=-1;
	rear++;
	qx[rear]=x;
	qy[rear]=y;
	qz[rear]=z;
}

void BFS(int x, int y, int z){
	front = rear = -1;
	//visit[x][y][z] = true;
	buoc[x][y][z] = 0;
	PUSH(x, y, z);

	while(front!=rear){
		POP();
		int tempx = qx[front];
		int tempy = qy[front];
		int tempz = qz[front];

		for(int i=0;i<6;i++){
			int stepx = tempx + dx[i];
			int stepy = tempy + dy[i];
			int stepz = tempz + dz[i];

			if(check(stepx, stepy, stepz) /*&& visit[stepx][stepy][stepz]==false*/){
				//visit[stepx][stepy][stepz]=true;

				if(visit[stepx][stepy][stepz]==true){
					if(buoc[stepx][stepy][stepz] > buoc[tempx][tempy][tempz]+map[stepx][stepy][stepz]){
						PUSH(stepx, stepy, stepz);
						buoc[stepx][stepy][stepz] = buoc[tempx][tempy][tempz]+map[stepx][stepy][stepz];
					}
				}
				else {
					visit[stepx][stepy][stepz]=true;
					PUSH(stepx, stepy, stepz);
					buoc[stepx][stepy][stepz] = buoc[tempx][tempy][tempz]+map[stepx][stepy][stepz];

				}
				if(stepx==1 || stepx==N || stepy==1 || stepz==1 || stepz==N){
					if(mindem > buoc[stepx][stepy][stepz]){
						mindem = buoc[stepx][stepy][stepz];
					}
				}
			}
		}
	}
}




int main(){
	freopen("tep.txt", "r", stdin);
	cin>>T;
	for(int t=1;t<=T;t++){
		cin>>N;
		//cout<<N<<endl;
		for(int x=1;x<=N;x++){
			for(int y=1;y<=N;y++){
				for(int z=1;z<=N;z++){
					cin>>map[x][y][z];
					//visit[x][y][z] = false;
					buoc[x][y][z] = maxS;
					if(map[x][y][z]==2){
						strx = x;
						stry = y;
						strz = z;
					}
				}
			}
		}
		mindem = maxS;
		BFS(strx, stry, strz);
		cout<<"#"<<t<<" "<<mindem<<endl;
	}

	return 0;
}
Leave a Comment