Note 6:

Revision en1, by NeoYL, 2024-01-01 16:30:11

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

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.

Tags bfs, multisource bfs, logical thinking, dfs and similar

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en12 English NeoYL 2024-01-01 19:22:52 9 Tiny change: 'lacement ('.' to '#'' -> 'lacement (changing '.' to '#''
en11 English NeoYL 2024-01-01 18:42:25 52
en10 English NeoYL 2024-01-01 18:40:15 10
en9 English NeoYL 2024-01-01 18:38:50 1377
en8 English NeoYL 2024-01-01 18:20:50 2 Tiny change: 'oiler>\n\n\n<spoil' -> 'oiler>\n\n<spoil'
en7 English NeoYL 2024-01-01 16:36:38 10 Tiny change: 'er of '.' &mdash; **Min** b' -> 'er of '.' $-$ **Min** b'
en6 English NeoYL 2024-01-01 16:35:19 2 Tiny change: 'k it's $*2400$ to $*2' -> 'k it's $*2300$ to $*2'
en5 English NeoYL 2024-01-01 16:34:31 28 Tiny change: 'laced $=$ **Min** b' -> 'laced $=$ Total number of '.' - **Min** b'
en4 English NeoYL 2024-01-01 16:33:00 7 Tiny change: 't's $*2400~*2500$\n</' -> 't's $*2400$ to $*2500$\n</'
en3 English NeoYL 2024-01-01 16:32:32 84
en2 English NeoYL 2024-01-01 16:30:59 36
en1 English NeoYL 2024-01-01 16:30:11 3653 Initial revision (published)