Tomb Hater
Time limit4sMemory limit1024 MB
Find a shortest north-to-south path on a grid that spells a concatenation of given words, moving only south, west, or east without revisiting tiles.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Graph, Trie, Shortest path
- Solved
- No attempts yet
Problem
You've discovered the long-lost tomb of the great pharaoh T'om Bha Ter. After eluding a devious sequence of snake traps, boulder traps, ant traps, sand traps and speed traps, you've about had it with traps. Only one challenge remains between you and a hoard of priceless, museum-belonging-in artifacts. You enter a room from the North whose floor is a rectangular grid, each tile of which is inscribed with a glyph. A small plaque contains a list of glyph words (constructed from individual glyphs in a specified order) and the following brief set of instructions:
- From any given tile you may only move one tile to the South, West or East.
- You may not step on a tile more than once.
- The path you take must spell out a sequence of complete glyph words from the given list (repetition of glyph words is allowed).
- If multiple paths exist, you must find the path that steps on the least number of tiles.
Disobey any of these rules and you'll find yourself hurtling into a bottomless abyss. Since you brought your laptop, you immediately get to coding.
Input
Input starts with a line containing three positive integers (), where and are the dimensions of the rectangular grid and is the number of glyph words. The next lines contain upper-case letters, separated by single spaces, representing the rectangular grid. The next lines each contain a glyph word, also consisting entirely of capital letters. Each glyph word will contain at most letters.
Output
If there is a route that starts at any Northernmost tile, ends at any Southernmost tile, and obeys all of the above rules, output the length of the shortest such route. Otherwise output impossible.