This is my personal note and might be some kind of user editorial/learning material for some people!
This is the sixth episode of this "note" series. I will write notes on problems (normally around 2400-ish problems), that are both interesting and educational. I normally will spend a few hours on each problem so please be patient when reading the blog.
If you want to motivate me to write a continuation (aka note 7), a significant upvote from you would be well appreciated! If I received lots of downvotes (because I'm also spending a lot of time to write this and to learn latex only to express my ideas accurately to you guys), I'm probably not gonna continuing writing these blogs.
Difficulty rating$$$*2600$$$ but I personally think it's $$$*2400$$$ to $$$*2500$$$
TagsMultisource BFS and simple BFS
Problem link
Problem paraphrased:
Given a $$$N*M$$$ grid. Cell '.' denotes an empty cell, '#' denotes a wall and 'V' would the the starting position.
An exit is a cell with $$$.$$$ and is at the edge of the grid.
Type 1: grids with $$$V$$$ not able to visit any exits.
Type 2: grids with $$$V$$$ only able to visit exactly one exit.
Type 3: grids with $$$V$$$ able to visit $$$\geq 2$$$ exits
Find maximum replacement ('.' to '#') such that the type of grid remains the same.
Clearly we can seperate into 3 cases:
Type 1 hintDoes placing a block in an empty cell matter?
Type 1This task is simple, since blocking every cell is the optimal solution. This is because it cannot escape anyway so just cover everything.
Type 2 hintMax number of block placed $$$=$$$ Total number of '.' — Min blocks needed to move to an exit.
Type 2This task is also relatively simple, since Max number of block placed $$$=$$$ Min blocks needed to move to an exit. We can simply find the shortest path from $$$V$$$ to the only exit and just cover the other unused blocks
Type 3 hintIt is easy to observe that we don't need all exits. We only need 2.
Maybe we consider moving to a cell $$$(i,j)$$$ first then we split into 2 paths going to 2 exits?
Type 3This is task is what makes the problem hard. We notice that we can always consider moving to a cell $$$(i,j)$$$ first then then we split into 2 paths going to 2 exits.
So, we need to find two closest exits to a cell and that can be performed using a multisource $$$BFS$$$. Also note that we also have to make sure the same exit isn't recorded twice. That inspires us to let $$$who_{x,y,0/1} = $$$ id of exit. The rest is just implementation.
Note: make sure to set who is going to a cell before throwing it into the queue, or else you would get TLE like me.
Phew, finally finished the problem~
FeelingsAmazing problem, somehow looks familiar for me.
Anyways, I had the idea of converting the grid into a graph with $$$N*M$$$ nodes and adding an edge of where it came from in the $$$BFS$$$ from $$$V$$$. Then convert the graph to $$$DAG$$$ then we can perform $$$DP$$$ on the $$$DAG$$$. Then I noticed that it is quite hard to do so, while I'm currently still doubting it'll work or not.
It is rather implementation heavy for me so even though I had the idea from like the beginning, I needed many submissions to pass.
AC code link
The code looks slightly ugly, hope you guys can comprehend it.
Hope you guys learnt something from the blog. Thank you for reading.