864. Shortest Path to Get All Keys
864. Shortest Path to Get All Keys
题目
We are given a 2-dimensional grid. "." is an empty cell, "#" is a wall, "@" is the starting point, ( "a", "b", ...) are keys, and ( "A", "B", ...) are locks.
We start at the starting point, and one move consists of walking one space in one of the 4 cardinal directions. We cannot walk outside the grid, or walk into a wall. If we walk over a key, we
pick it up. We can't walk over a lock unless we have the corresponding key.
For some 1 <= K <= 6, there is exactly one lowercase and one uppercase letter of the first K letters of the English alphabet in the grid. This means that there is exactly one key for each lock,
and one lock for each key; and also that the letters used to represent the keys and locks were chosen in the same order as the English alphabet.
Return the lowest number of moves to acquire all keys. If it's impossible, return -1.
Example 1:
Input: ["@.a.#","###.#","b.A.B"] Output: 8
Example 2:
Input: ["@..aA","..B#.","....b"] Output: 6
Note:
- 1 <= grid.length <= 30
- 1 <= grid[0].length <= 30
- grid[i][j] contains only '.', '#', '@', 'a'-'f' and 'A'-'F'
- The number of keys is in [1, 6]. Each key has a different letter and opens exactly one lock.
题目大意
给定一个二维网格 grid。 "." 代表一个空房间, "#" 代表一堵墙, "@" 是起点,("a", "b", ...)代表钥匙,("A", "B", ...)代表锁。
我们从起点开始出发,一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走,也无法穿过一堵墙。如果途经一个钥匙,我们就把它捡起来。除非我们手里有对应的钥匙,否则无
法通过锁。
全站分卷索引 · 462 卷
- 1532. K-diff Pairs in an Array
- 2题目大意
- 3537. Complex Number Multiplication
- 4541. Reverse String II
- 5解题思路
- 6题目大意
- 7代码
- 8547. Friend Circles
- 9解题思路
- 10557. Reverse Words in a String III
- 11代码
- 12题目大意
- 13题目
- 14566. Reshape the Matrix
- 15题目大意
- 16代码
- 17题目大意
- 18572. Subtree of Another Tree
- 19题目大意
- 20575. Distribute Candies
- 21题目大意
- 22解题思路
- 23题目大意
- 24代码
- 25题目大意
- 26628. Maximum Product of Three Numbers
- 27632. Smallest Range Covering Elements from K Lists
- 28代码
- 29633. Sum of Square Numbers
- 30解题思路
- 31题目大意
- 32代码
- 33637. Average of Levels in Binary Tree
- 34638. Shopping Offers
- 35题目大意
- 36解题思路
- 37645. Set Mismatch
- 38题目大意
- 39648. Replace Words
- 40653. Two Sum IV - Input is a BST
- 41题目大意
- 42题目大意
- 43代码
- 44题目大意
- 45662. Maximum Width of Binary Tree
- 46题目大意
- 47代码
- 48668. Kth Smallest Number in Multiplication Table
- 49题目大意
- 50676. Implement Magic Dictionary
- 51题目大意
- 52682. Baseball Game
- 53题目大意
- 54684. Redundant Connection
- 55题目大意
- 56解题思路
- 57题目大意
- 58代码
- 59693. Binary Number with Alternating Bits
- 60题目大意
- 61695. Max Area of Island
- 62题目大意
- 63697. Degree of an Array
- 64代码
- 65题目大意
- 66解题思路
- 67代码
- 68704. Binary Search
- 69代码
- 70题目大意
- 71706. Design HashMap
- 72题目大意
- 73707. Design Linked List
- 74题目大意
- 75710. Random Pick with Blacklist
- 76题目大意
- 77代码
- 78713. Subarray Product Less Than K
- 79代码
- 80题目大意
- 81715. Range Module
- 82题目大意
- 83717. 1-bit and 2-bit Characters
- 84题目大意
- 85题目大意
- 86719. Find K-th Smallest Pair Distance
- 87题目大意
- 88720. Longest Word in Dictionary
- 89题目大意
- 90721. Accounts Merge
- 91题目大意
- 92代码
- 93725. Split Linked List in Parts
- 94题目大意
- 95726. Number of Atoms
- 96题目大意
- 97解题思路
- 98729. My Calendar I
- 99题目大意
- 100解题思路
- 101732. My Calendar III
- 102题目大意
- 103解题思路
- 104733. Flood Fill
- 105解题思路
- 106题目
- 107题目大意
- 108739. Daily Temperatures
- 109744. Find Smallest Letter Greater Than Target
- 110题目大意
- 111745. Prefix and Suffix Search
- 112解题思路
- 113746. Min Cost Climbing Stairs
- 114题目大意
- 115748. Shortest Completing Word
- 116题目大意
- 117753. Cracking the Safe
- 118题目大意
- 119756. Pyramid Transition Matrix
- 120题目大意
- 121代码
- 122题目大意
- 123763. Partition Labels
- 124解题思路
- 125765. Couples Holding Hands
- 126题目大意
- 127代码
- 128题目大意
- 129767. Reorganize String
- 130代码
- 131771. Jewels and Stones
- 132代码
- 133题目大意
- 134代码
- 135781. Rabbits in Forest
- 136题目大意
- 137784. Letter Case Permutation
- 138786. K-th Smallest Prime Fraction
- 139题目大意
- 140793. Preimage Size of Factorial Zeroes Function
- 141解题思路
- 142代码
- 143802. Find Eventual Safe States
- 144解题思路
- 145题目大意
- 146解题思路
- 147811. Subdomain Visit Count
- 148题目
- 149解题思路
- 150812. Largest Triangle Area
- 151题目大意
- 152815. Bus Routes
- 153代码
- 154817. Linked List Components
- 155解题思路
- 156819. Most Common Word
- 157题目大意
- 158826. Most Profit Assigning Work
- 159代码
- 160828. Unique Letter String
- 161代码
- 162832. Flipping an Image
- 163题目大意
- 164题目大意
- 165836. Rectangle Overlap
- 166解题思路
- 167题目大意
- 168839. Similar String Groups
- 169题目大意
- 170841. Keys and Rooms
- 171题目大意
- 172842. Split Array into Fibonacci Sequence
- 173题目大意
- 174844. Backspace String Compare
- 175题目大意
- 176845. Longest Mountain in Array
- 177题目大意
- 178850. Rectangle Area II
- 179题目大意
- 180代码
- 181851. Loud and Rich
- 182题目大意
- 183解题思路
- 184852. Peak Index in a Mountain Array
- 185解题思路
- 186853. Car Fleet
- 187题目大意
- 188856. Score of Parentheses
- 189题目大意
- 190862. Shortest Subarray with Sum at Least K
- 191题目大意
- 192863. All Nodes Distance K in Binary Tree
- 193题目大意
- 194代码
- 195864. Shortest Path to Get All Keys
- 196解题思路
- 197867. Transpose Matrix
- 198872. Leaf-Similar Trees
- 199题目大意
- 200代码
- 201题目大意
- 202876. Middle of the Linked List
- 203题目大意
- 204878. Nth Magical Number
- 205题目大意
- 206880. Decoded String at Index
- 207题目大意
- 208881. Boats to Save People
- 209解题思路
- 210题目大意
- 211885. Spiral Matrix III
- 212题目大意
- 213887. Super Egg Drop
- 214题目大意
- 215代码
- 216题目
- 217解题思路
- 218891. Sum of Subsequence Widths
- 219代码
- 220题目大意
- 221895. Maximum Frequency Stack
- 222题目大意
- 223解题思路
- 224896. Monotonic Array
- 225题目大意
- 226897. Increasing Order Search Tree
- 227解题思路
- 228898. Bitwise ORs of Subarrays
- 229题目大意
- 230代码
- 231901. Online Stock Span
- 232题目大意
- 233904. Fruit Into Baskets
- 234题目大意
- 235907. Sum of Subarray Minimums
- 236代码
- 237911. Online Election
- 238解题思路
- 239914. X of a Kind in a Deck of Cards
- 240题目大意
- 241918. Maximum Sum Circular Subarray
- 242题目大意
- 243代码
- 244题目大意
- 245代码
- 246921. Minimum Add to Make Parentheses Valid
- 247题目大意
- 248题目大意
- 249题目
- 250924. Minimize Malware Spread
- 251题目大意
- 252解题思路
- 253925. Long Pressed Name
- 254题目大意
- 255927. Three Equal Parts
- 256题目大意
- 257928. Minimize Malware Spread II
- 258题目大意
- 259解题思路
- 260930. Binary Subarrays With Sum
- 261代码
- 262题目大意
- 263942. DI String Match
- 264代码
- 265题目大意
- 266题目
- 267代码
- 268题目大意
- 269952. Largest Component Size by Common Factor
- 270题目大意
- 271代码
- 272953. Verifying an Alien Dictionary
- 273题目大意
- 274959. Regions Cut By Slashes
- 275题目大意
- 276代码
- 277961. N-Repeated Element in Size 2N Array
- 278代码
- 279题目大意
- 280代码
- 281969. Pancake Sorting
- 282题目大意
- 283970. Powerful Integers
- 284题目大意
- 285973. K Closest Points to Origin
- 286题目大意
- 287976. Largest Perimeter Triangle
- 288题目大意
- 289题目大意
- 290978. Longest Turbulent Subarray
- 291题目大意
- 292979. Distribute Coins in Binary Tree
- 293题目大意
- 294代码
- 295980. Unique Paths III
- 296题目大意
- 297981. Time Based Key-Value Store
- 298题目大意
- 299解题思路
- 300984. String Without AAA or BBB
- 301题目大意
- 302985. Sum of Even Numbers After Queries
- 303题目大意
- 304986. Interval List Intersections
- 305代码
- 306题目大意
- 307解题思路
- 308题目
- 309代码
- 310993. Cousins in Binary Tree
- 311题目大意
- 312解题思路
- 313995. Minimum Number of K Consecutive Bit Flips
- 314题目大意
- 315代码
- 316996. Number of Squareful Arrays
- 317代码
- 318999. Available Captures for Rook
- 319题目大意
- 320解题思路
- 3211002. Find Common Characters
- 3221003. Check If Word Is Valid After Substitutions
- 323题目大意
- 324解题思路
- 3251004. Max Consecutive Ones III
- 3261005. Maximize Sum Of Array After K Negations
- 327题目大意
- 3281011. Capacity To Ship Packages Within D Days
- 329题目大意
- 3301017. Convert to Base -2
- 331解题思路
- 332题目大意
- 3331020. Number of Enclaves
- 334题目大意
- 3351021. Remove Outermost Parentheses
- 336题目大意
- 337代码
- 3381025. Divisor Game
- 339代码
- 340题目大意
- 341解题思路
- 342题目大意
- 343解题思路
- 3441030. Matrix Cells in Distance Order
- 345题目大意
- 346代码
- 347题目大意
- 348题目大意
- 349代码
- 3501047. Remove All Adjacent Duplicates In String
- 351题目大意
- 3521049. Last Stone Weight II
- 353代码
- 354题目大意
- 3551052. Grumpy Bookstore Owner
- 356解题思路
- 3571054. Distant Barcodes
- 358题目大意
- 3591073. Adding Two Negabinary Numbers
- 360题目大意
- 361代码
- 3621074. Number of Submatrices That Sum to Target
- 363解题思路
- 3641078. Occurrences After Bigram
- 365解题思路
- 366题目大意
- 3671089. Duplicate Zeros
- 3681093. Statistics from a Large Sample
- 369题目大意
- 3701105. Filling Bookcase Shelves
- 371题目大意
- 3721108. Defanging an IP Address
- 373代码
- 374题目大意
- 3751111. Maximum Nesting Depth of Two Valid Parentheses Strings
- 376题目大意
- 377代码
- 3781122. Relative Sort Array
- 379解题思路
- 3801123. Lowest Common Ancestor of Deepest Leaves
- 381题目大意
- 3821128. Number of Equivalent Domino Pairs
- 383解题思路
- 384题目大意
- 3851145. Binary Tree Coloring Game
- 386题目大意
- 387解题思路
- 3881154. Day of the Year
- 389题目大意
- 390题目
- 391解题思路
- 392代码
- 3931160. Find Words That Can Be Formed by Characters
- 394解题思路
- 395题目大意
- 396代码
- 397题目大意
- 3981175. Prime Arrangements
- 399题目大意
- 4001184. Distance Between Bus Stops
- 401题目大意
- 402解题思路
- 403题目大意
- 404题目
- 405代码
- 406题目大意
- 4071201. Ugly Number III
- 408解题思路
- 409题目大意
- 410解题思路
- 4111207. Unique Number of Occurrences
- 4121208. Get Equal Substrings Within Budget
- 413题目大意
- 4141217. Play with Chips
- 415题目大意
- 416题目
- 417代码
- 418题目大意
- 419解题思路
- 420题目大意
- 421代码
- 422题目大意
- 4231252. Cells with Odd Values in a Matrix
- 424题目大意
- 425解题思路
- 4261254. Number of Closed Islands
- 427题目大意
- 4281260. Shift 2D Grid
- 429题目大意
- 430代码
- 431题目大意
- 432题目大意
- 433代码
- 4341281. Subtract the Product and Sum of Digits of an Integer
- 4351283. Find the Smallest Divisor Given a Threshold
- 436题目大意
- 4371287. Element Appearing More Than 25% In Sorted Array
- 4381290. Convert Binary Number in a Linked List to Integer
- 439题目大意
- 440题目大意
- 4411299. Replace Elements with Greatest Element on Right Side
- 4421300. Sum of Mutated Array Closest to Target
- 443解题思路
- 4441302. Deepest Leaves Sum
- 4451304. Find N Unique Integers Sum up to Zero
- 446解题思路
- 447题目大意
- 448解题思路
- 449题目大意
- 4501313. Decompress Run-Length Encoded List
- 451解题思路
- 452题目大意
- 4531380. Lucky Numbers in a Matrix
- 454题目大意
- 4551385. Find the Distance Value Between Two Arrays
- 456题目大意
- 4571389. Create Target Array in the Given Order
- 458题目大意
- 459题目大意
- 460题目大意
- 4611470. Shuffle the Array
- 462解题思路