Note 6: Codeforces CF1898F Div 2 [Easy]

Правка en7, от NeoYL, 2024-01-01 16:36:38

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
Tags

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 hint
Type 1
Type 2 hint
Type 2
Type 3 hint
Type 3

Phew, finally finished the problem~

Feelings

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.

Теги bfs, multisource bfs, logical thinking, dfs and similar

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en12 Английский NeoYL 2024-01-01 19:22:52 9 Tiny change: 'lacement ('.' to '#'' -> 'lacement (changing '.' to '#''
en11 Английский NeoYL 2024-01-01 18:42:25 52
en10 Английский NeoYL 2024-01-01 18:40:15 10
en9 Английский NeoYL 2024-01-01 18:38:50 1377
en8 Английский NeoYL 2024-01-01 18:20:50 2 Tiny change: 'oiler>\n\n\n<spoil' -> 'oiler>\n\n<spoil'
en7 Английский NeoYL 2024-01-01 16:36:38 10 Tiny change: 'er of '.' &mdash; **Min** b' -> 'er of '.' $-$ **Min** b'
en6 Английский NeoYL 2024-01-01 16:35:19 2 Tiny change: 'k it's $*2400$ to $*2' -> 'k it's $*2300$ to $*2'
en5 Английский NeoYL 2024-01-01 16:34:31 28 Tiny change: 'laced $=$ **Min** b' -> 'laced $=$ Total number of '.' - **Min** b'
en4 Английский NeoYL 2024-01-01 16:33:00 7 Tiny change: 't's $*2400~*2500$\n</' -> 't's $*2400$ to $*2500$\n</'
en3 Английский NeoYL 2024-01-01 16:32:32 84
en2 Английский NeoYL 2024-01-01 16:30:59 36
en1 Английский NeoYL 2024-01-01 16:30:11 3653 Initial revision (published)