saving visited 3D coordinates?

Правка en1, от hiddentesla, 2016-07-29 13:05:21

problem:

given a block with with bottom corner at (1,1,1) and uppper corner at (P,L,T) (2<=P,L,T<=400), a starting coordinate (x1,y1,z1) and target coordinate (x2,y2,z2)

find the shortest distance needed to get from (x1,y1,z1) to (x2,y2,z2) by only moving in the sides of the block

it is guaranteed that the starting and ending coordinates are located in the sides of the block (meaning atleast one of x,y,z is either 1 or P,L,T)

i know there is a math solution (with lots of if's), but given the constraints, and me wanting to learn something new, i wanted to solve this problem with BFS

so max test is where P=L=T=400, and we needed to get from (1,1,1) to (400,400,400) there should be only 6*400*400 = 960000 states. so my bfs algo is as follows:

//make struct node to save the x,y,z coordinate

queue q; while(!q.empty()) node t=q.front(); q.pop(); if(t is the target coordinate) print how many steps else if(t is not visited yet) visit all neighbours of t

the problem is the part if(t is not visited yet)

im having troubles finding a data structure/method that can save visited coordinates efficiently

i made comparing struct to compare based on x, then y, then z

i tried std::set but it got TLE'd

i also tried std::map<node,bool> but it also got TLE

so im asking, is there a method/data structure that can save visited 3D coordinates?

Теги data structures, bfs

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский hiddentesla 2016-07-29 13:05:21 1435 Initial revision (published)