I recently solved https://cses.fi/problemset/task/1193/, and I found that using pointers here was a natural way to efficiently keep track of the shortest path. At first I had a vector of type obj, each of which contained a pointer to the type obj, but I soon learned that these objects were not actually returning their own memory location! Instead they seemed to take on the memory location of the front of the queue. To try and fix this, I changed it to be a queue of type obj*, but now I could no longer add things to the queue like this q.push({0,0,"",nullptr}), instead I could only get it to work by adding a constructor to obj, and building objects on the heap. Am I missing a simpler/elegant way of doing this?
The solution in question: https://cses.fi/paste/0c68129b81b0a8252c88f4/
You are right indeed. Your solution effectively mixes a linked list with a queue, and the most elegant way to do this is to store the data somewhere else (e.g. on the heap) and use pointers to refer to the data from both the linked list (like you do with
obj* o) and the queue (like you do withqueue<obj*> q).An alternative solution is to store all the objects in a
vector<obj>and use offsets into this vector instead of pointers. This would allow you to halve the memory usage of the queue and also easily clean up the objects after the computations.Note that you could store the direction you visit each cell individually using a simple char, (q.push(1,0,'D')). Answer is extracted by traversing from B to A using a stack.