### hiddentesla's blog

By hiddentesla, history, 8 years ago,

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?

• -7

 » 8 years ago, # |   0 Can you share the link to the problem ?
•  » » 8 years ago, # ^ |   +1 sorry, its in my native languange :(
 » 8 years ago, # |   +11 You can use a 400 × 400 × 400 boolean array. It's just 64 million values, and can be further packed to fit in 8 million bytes.
•  » » 8 years ago, # ^ |   +9 how to make it fit in 8 million bytes?
•  » » » 8 years ago, # ^ |   +9
•  » » » » 8 years ago, # ^ |   +8 thanks, i did not know bitset existed xDso bitset can only take constants right?you cant declare something like bitset visited?but i did get arround it by using a hash function to hash the coordinates, again thank you very much