EllysBreakout
2022 HF Qual · 2022-03-16 · by espr1t
2022 HF Qual · 2022-03-16 · by espr1t · Graph Theory, Search
Problem Statement
Problem Statement
Elly was kidnapped! Luckily she has found the plan of the mansion she is held hostage at. Unfortunately she does not know where exactly in the building she is located (she was blind-folded when taken there).
We can consider the mansion to be a matrix of N rows and M columns. Each cell can either be empty (a corridor) or blocked (a wall). Initially Elly is located in one of the empty cells, but we don't know which one exactly. She can move to each of the (up to) four adjacent cells. Moving to adjacent empty cell takes no time at all - after all it's just making several steps. Moving through a blocked cell takes a bit more time - the girl has to break the wall first. We assume that this takes her one hour. The girl can escape through each of the cells on the border of the mansion by just stepping out (like there is a corridor outside the matrix).
Elly believes she is located in an empty cell that would take her the most time to break free, if choosing the optimal path out. Help her by finding out how many possibile such cells there are.
You are given the plan of the mansion in theString[] plan. It has N elements (the rows of the matrix), and each element is M characters long (the columns of the matrix). Each character is either a '.' or '#'. The symbol '.' represents an empty cell and the symbol '#' represents a blocked cell. Write a method that returns the number of cells that the girl can be initially located in - that is the number of cells, that have maximal time to reach the outside of the mansion if choosing the optimal path.
We can consider the mansion to be a matrix of N rows and M columns. Each cell can either be empty (a corridor) or blocked (a wall). Initially Elly is located in one of the empty cells, but we don't know which one exactly. She can move to each of the (up to) four adjacent cells. Moving to adjacent empty cell takes no time at all - after all it's just making several steps. Moving through a blocked cell takes a bit more time - the girl has to break the wall first. We assume that this takes her one hour. The girl can escape through each of the cells on the border of the mansion by just stepping out (like there is a corridor outside the matrix).
Elly believes she is located in an empty cell that would take her the most time to break free, if choosing the optimal path out. Help her by finding out how many possibile such cells there are.
You are given the plan of the mansion in the
Constraints
- plan will contain between 1 and 100 elements, inclusive.
- Each element of plan will contain between 1 and 100 characters, inclusive.
- All elements of plan will contain the same number of characters.
- Each character in plan will be either '.' or '#'.
- It is guaranteed, that there will be at least one '.' character.
Examples
0)
{".#............",
".#####........",
".#.#..#.......",
".##.#.#.......",
".#.#..#..####.",
".#...##..#.##.",
"..####...###.."}
Returns: 1
There are three "rooms", one of them nested inside another one. This means the girl should be located inside the inner room (she needs to break two walls to escape).
1)
{"..#",
"...",
".#."}
Returns: 7
Sometimes Elly may be able to escape without breaking any walls.
2)
{"#.#.#.#.#.#.#.#.#.",
".#.#.#.#.#.#.#.#.#",
"#.#.#.#.#.#.#.#.#.",
".#.#.#.#.#.#.#.#.#",
"#.#.#.#.#.#.#.#.#.",
".#.#.#.#.#.#.#.#.#",
"#.#.#.#.#.#.#.#.#.",
".#.#.#.#.#.#.#.#.#",
"#.#.#.#.#.#.#.#.#.",
".#.#.#.#.#.#.#.#.#",
"#.#.#.#.#.#.#.#.#.",
".#.#.#.#.#.#.#.#.#"}
Returns: 8
Please note that the girl can only move horizontally and vertically (but not diagonally).
3)
{"#########",
"#########",
"#########",
"#########",
"####.####",
"####.####",
"####.####",
"#########",
"#########",
"#########",
"#########"}
Returns: 3
Very well guarded room with three cells.
4)
{"#...##.......#..#..#..#.#..#..###............##...",
"....#.....#....#...###..#....#......#.#.......#.#.",
"......#....#..#.....#.#..#...#.#..##.......#.....#",
"................#..#......##........#..#....##...#",
"###..#..#.#....##...#...........#.##..###..##.....",
".##..#......#...........#.##...##..#.....#.....#..",
"....#..##...#..#.#........##.#....................",
".#.#.#.##.....#.........#......#.......#..#.##.#..",
"..#....#......#........#...#.#...#.#....#........#",
"#.#....#..#.#.#.#....#.....................#.#....",
".#....#..#.......#.........#....#.#............##.",
"..##......#....###..#...#.#..#.....##........#..#.",
"........#.#..........#......#........##.#.#.#....#",
"....#.#..####...#..#.....#.###..##....#.#.......#.",
"....#....#...#................###.#......##.......",
".#.....#..#.....##....#......................##.#.",
"#.................#.......#...#...........#....#..",
"............#........#.....#.#.....#.#.....#..##..",
"#......#.#..#.#.##..#.........#..#.#.....#.....#..",
"....#..###.#........#.#.....................##....",
"......##...###..#...#.##..#..#.##....#.........##.",
".......#...............#....#...#......##....#..#.",
".#...#.##....#...#........###..##.#....#...##.....",
"....#........#..............#..###.#.#..#.....#.##",
".#...#..#.....#.#...#...........#....##.....#.#...",
"...#..#.#.#..##....#............#.....#........###",
".##......#.#..##.......###...##...................",
"..........#.............#.#...#.....###...##..##..",
".......##...#.#...#.........#.#.....#.#..#.#...#..",
"####.........#.#.....#....#.#......#.#.....#..#...",
".#.#...#..###...#.#.#.....###.#....##.....#...#..#",
".#..#.##.#.###....#.###..#..........#...#.........",
"##..#.#....#..##...#.....##..#..##..............##",
"#.##.##..........##.#....##......#...#.....##...#.",
".....#........#..............#.....####.######....",
"..##............#..###.##...#.#...#.....#.#...#..#",
"...##..#.#...#......#.#..........#..#..##..#.#..#.",
"..##.####......#....#....#.....#......#....##.....",
"#.......####.#......##.#.....#..#........#...##.#.",
"..#.....#..###....#......#..#........#....####....",
"......#.....#..................#.........#.##...#.",
"...#....#....##......#.#.....#.....#....#......#..",
"....#.##...#.#....#..#.#...#.......##.......#.#...",
"...#..#.#.##.#.....###....#.###.....##.#......#...",
".#.#......#.....#.....#...........##...#.....#.##.",
"..........#.....#...#.##....#..........#.....###..",
"........##..#.....#...#....##..#......##.......#..",
".....#....##....#.....#....#.#.#.........#........",
"..#...##......#.#............#....#.##...#....#...",
"..##...#.#...#......#....##.#.#..#......#..######."}
Returns: 13
Submissions are judged against all 110 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class EllysBreakout with a public method int getCount(vector<string> plan) · 110 test cases · 2 s / 256 MB per case