Table of Contents
Leetcode 1730. Shortest Path to Get Food
Problem
You are starving and you want to eat food as quickly as possible. You want to find the shortest path to arrive at any food cell.
You are given an m x n
character matrix, grid
, of these different types of cells:
'*'
is your location. There is exactly one'*'
cell.'#'
is a food cell. There may be multiple food cells.'O'
is free space, and you can travel through these cells.'X'
is an obstacle, and you cannot travel through these cells.
You can travel to any adjacent cell north, east, south, or west of your current location if there is not an obstacle.
Return the length of the shortest path for you to reach any food cell. If there is no path for you to reach food, return -1
.
Example 1:
Input: grid = [["X","X","X","X","X","X"],["X","*","O","O","O","X"],["X","O","O","#","O","X"],["X","X","X","X","X","X"]] Output: 3 Explanation: It takes 3 steps to reach the food.
Example 2:
Input: grid = [["X","X","X","X","X"],["X","*","X","O","X"],["X","O","X","#","X"],["X","X","X","X","X"]] Output: -1 Explanation: It is not possible to reach the food.
Example 3:
Input: grid = [["X","X","X","X","X","X","X","X"],["X","*","O","X","O","#","O","X"],["X","O","O","X","O","O","X","X"],["X","O","O","O","O","#","O","X"],["X","X","X","X","X","X","X","X"]] Output: 6 Explanation: There can be multiple food cells. It only takes 6 steps to reach the bottom food.
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 200
grid[row][col]
is'*'
,'X'
,'O'
, or'#'
.- The
grid
contains exactly one'*'
.
Source: Leetcode 1730. Shortest Path to Get Food
Solution
This problem can be solved by a straight forward implementation of Breadth First Search algorithm. If we were asked to take all the foods with minimum length, the story would have been different though.
To apply BFS, we can take a queue and push the coordinates of source. Until we reach the coordinate of a single food, we will continue exploring neighbour nodes and push into the queue.
During this process, we will also keep track of distance passed so far. Once one of the food coordinates is found, we will return the destination so far plus one.
Below code is pretty simple to understand the above algorithm.
C++ Code
class Solution { public: int getFood(vector<vector<char>>& grid) { queue<pair<int, int>> q; int R = grid.size(); if(R == 0) return -1; int C = grid[0].size(); if(C == 0) return -1; vector<vector<int>> visited(R, vector<int>(C, 0)); for(int i = 0; i < R; i++){ for(int j = 0; j < C; j++){ if(grid[i][j] == '*'){ q.push({i, j}); visited[i][j] = 1; break; } } } vector<vector<int>> dir{ {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; int distance = 0; while(!q.empty()){ int len = q.size(); for(int l = 0; l < len; l++){ pair<int, int> pr = q.front(); q.pop(); for(int i = 0; i < 4; i++){ int r = pr.first + dir[i][0]; int c = pr.second + dir[i][1]; if(0 <= r && r < R && 0 <= c && c < C){ if(grid[r][c] == '#') return distance + 1; if(grid[r][c] == 'O' && visited[r][c] == 0){ q.push({r, c}); visited[r][c] = 1; } } } } distance += 1; } return -1; } };
Conclusion
Hope you enjoyed this simple article about “Leetcode 1730. Shortest Path to Get Food.” Please leave a message for your valuable insights about this blog. Also, please feel free to browse other articles.
Happy coding! 🙂
Your article gave me a lot of inspiration, I hope you can explain your point of view in more detail, because I have some doubts, thank you.
Dear foolishhungry.com webmaster, You always provide clear explanations and step-by-step instructions.
Hi foolishhungry.com administrator, Thanks for the informative and well-written post!
Hello foolishhungry.com admin, Your posts are always well-supported and evidence-based.
To the foolishhungry.com owner, Your posts are always on point.
Hi foolishhungry.com owner, Your posts are always on point.
Hello foolishhungry.com admin, You always provide great resources and references.
To the foolishhungry.com webmaster, You always provide useful information.
To the foolishhungry.com webmaster, Thanks for the well-researched and well-written post!
One Click Vids is a content innovator! It’s turbocharged my YouTube and TikTok content and made affiliate promotions a money-spinner. Get in on this—affordable and incredibly intuitive!
One Click Vids is a creative powerhouse! It’s elevated my YouTube and TikTok game and made earning from affiliate offers a breeze. Dive into this gem—it’s affordable and ridiculously user-friendly!
Tiffany Cappotelli, Tiffany Cooper, Dren Lith Only Fans Leaks( https://picturesporno.com )
Can you be more specific about the content of your article? After reading it, I still have some doubts. Hope you can help me. https://accounts.binance.com/zh-TC/register-person?ref=UM6SMJM3
I am constantly looking online for ideas that can assist me. Thanks!
There are certainly lots of particulars like that to take into consideration. That may be a nice level to convey up. I offer the ideas above as normal inspiration but clearly there are questions just like the one you convey up where the most important factor might be working in sincere good faith. I don?t know if greatest practices have emerged round things like that, but I am sure that your job is clearly identified as a fair game. Both boys and girls really feel the impression of only a second’s pleasure, for the remainder of their lives.
Hi foolishhungry.com webmaster, Thanks for the well-organized post!
Of course like your website however you have to check the spelling on many of your posts. many of them are rife wih spelling issues and I find it very hard to inform the truth on the other hand I will likely come again again
I liked it as much as you did. Even though the picture and writing are good, you’re looking forward to what comes next. If you defend this walk, it will be pretty much the same every time.
Wonderful web site Lots of useful info here Im sending it to a few friends ans additionally sharing in delicious And obviously thanks to your effort
To the foolishhungry.com owner, Thanks for the well-written and informative post!
Thanks for sharing. I read many of your blog posts, cool, your blog is very good. https://www.binance.info/pt-PT/join?ref=DB40ITMB
I have been checking out some of your articles and i can claim nice stuff. I will make sure to bookmark your site.
To the foolishhungry.com webmaster, Thanks for the educational content!
I have read some excellent stuff here Definitely value bookmarking for revisiting I wonder how much effort you put to make the sort of excellent informative website
Your article helped me a lot, is there any more related content? Thanks! https://www.binance.com/ru/register?ref=S5H7X3LP
Your point of view caught my eye and was very interesting. Thanks. I have a question for you. https://accounts.binance.com/ru-UA/register-person?ref=IQY5TET4
Your article helped me a lot, is there any more related content? Thanks! https://accounts.binance.com/tr/register-person?ref=VDVEQ78S
I’ve been absent for some time, but now I remember why I used to love this web site. Thank you, I¦ll try and check back more often. How frequently you update your web site?
Thanx for the effort, keep up the good work Great work, I am going to start a small Blog Engine course work using your site I hope you enjoy blogging with the popular BlogEngine.net.Thethoughts you express are really awesome. Hope you will right some more posts.
I really like your writing style, wonderful info, appreciate it for putting up :D. “I hate mankind, for I think myself one of the best of them, and I know how bad I am.” by Joseph Baretti.
Your article helped me a lot, is there any more related content? Thanks!
I truly enjoy looking through on this website , it contains fantastic posts. “The longing to produce great inspirations didn’t produce anything but more longing.” by Sophie Kerr.
Today, I went to the beachfront with my children. I found a sea shell and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She put the shell to her ear and screamed. There was a hermit crab inside and it pinched her ear. She never wants to go back! LoL I know this is completely off topic but I had to tell someone!
Thanks for all your efforts that you have put in this. very interesting info .
Simply want to say your article is as astonishing. The clarity on your submit is simply great and that i can assume you’re an expert on this subject. Fine with your permission allow me to seize your RSS feed to keep updated with coming near near post. Thanks a million and please continue the rewarding work.
You actually make it appear so easy along with your presentation but I in finding this topic to be really one thing which I feel I might by no means understand. It seems too complicated and very huge for me. I’m having a look forward for your subsequent submit, I will try to get the grasp of it!
It’s a pity you don’t have a donate button! I’d definitely donate to this outstanding blog! I suppose for now i’ll settle for bookmarking and adding your RSS feed to my Google account. I look forward to new updates and will share this website with my Facebook group. Talk soon!
Thank you for the good writeup. It in reality was once a entertainment account it. Look complicated to more delivered agreeable from you! By the way, how can we be in contact?
Hi there! This post couldn’t be written any better! Reading through this post reminds me of my previous room mate! He always kept talking about this. I will forward this article to him. Pretty sure he will have a good read. Thank you for sharing!
Wonderful blog! I found it while searching on Yahoo News. Do you have any suggestions on how to get listed in Yahoo News? I’ve been trying for a while but I never seem to get there! Cheers
Heya i am for the primary time here. I came across this board and I in finding It truly helpful & it helped me out a lot. I’m hoping to provide one thing again and aid others like you helped me.
Very interesting points you have observed, thankyou for putting up.
You are a very bright person!
Appreciating the dedication you put into your blog and detailed information you offer. It’s nice to come across a blog every once in a while that isn’t the same unwanted rehashed material. Excellent read! I’ve saved your site and I’m including your RSS feeds to my Google account.
Thank you for your sharing. I am worried that I lack creative ideas. It is your article that makes me full of hope. Thank you. But, I have a question, can you help me?
Regards for this post, I am a big big fan of this site would like to keep updated.
I am not sure where youre getting your info but good topic I needs to spend some time learning much more or understanding more Thanks for magnificent info I was looking for this information for my mission
Ikaria Lean Belly Juice is a fast-acting weight loss supplement that is developed to incinerate stubborn fat.