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?
Can you share the link to the problem ?
sorry, its in my native languange :(
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.
how to make it fit in 8 million bytes?
https://en.wikipedia.org/wiki/Bit_array
thanks, i did not know bitset existed xD
so 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