Problem D from EWU contest, which we didn't even managed to try. During the contest, only Annihilator and Aeternitas managed to solve it. It asks you to find the shortest path between two grid points on a huge grid. There are some forbidden regions (these can be points, lines or filled rectangles). A classical problem of co-ordinate compression. I tried it later and got accepted after some unsuccessful tries.
What is co-ordinate compression?
Co-ordinate compression is a technique which is very commonly used in geometry problems. It simply replaces the k-th smallest ordinate with k (Or some way that the relative magnitude stays the same). For example you have a few points on a number line. -1, 5, 2, 17. The renumbered ordinates will be 1,3,2,4. The beauty of this technique is, for some problems we can actually look at important grid points rather than all - in a much smaller grid, solving the problem with much smaller space and time complexity.
Here is the code.
Mistakes I made:
1. Putting wrong indices: At several places I swapped x with y
2. Copy paste mistakes: Forgot to change things.
3. Making arbitrary changes hoping they would work but they didn't, and forgetting to change it back. This should end.
কোন মন্তব্য নেই:
একটি মন্তব্য পোস্ট করুন