Problem Statement
Note: This problem has a nonstandard time limit: 5 seconds.
You may have solved the following task before:
Given is an n by m board. Some cells of the board contain obstacles. Find the minimal number of obstacles one has to remove so that it will be possible to place a box onto the cell (0, 0) and then move it via some empty cells to (n-1, m-1) by repeatedly moving it by one cell up / down / left / right.
This task is very similar, but there is one difference: the box now has dimensions 2 by 2. We say that the box is at the position (x, y) when it occupies the cells (x, y), (x+1, y), (x, y+1) and (x+1, y+1). The box must start at (0, 0) and end at (n-2, m-2). At all moments, including the start and the end, all four cells occupied by the box must be empty (i.e., they may not contain any obstacles). At all moments, the whole box must be inside the board. In each step, we can only move the box up / down / left / right by one cell. That is, if we have the box at the position (x, y), we can move it to (x-1, y), (x+1, y), (x, y-1), or (x, y+1).
You are given the String[] board that describes the current state of the board: '#' is an obstacle, '.' is an empty cell. Find the minimal number of obstacles that have to be removed in order to create a board on which it is possible to move a 2x2 box from (0, 0) to (n-2, m-2) in the way described above.
You may have solved the following task before:
Given is an n by m board. Some cells of the board contain obstacles. Find the minimal number of obstacles one has to remove so that it will be possible to place a box onto the cell (0, 0) and then move it via some empty cells to (n-1, m-1) by repeatedly moving it by one cell up / down / left / right.
This task is very similar, but there is one difference: the box now has dimensions 2 by 2. We say that the box is at the position (x, y) when it occupies the cells (x, y), (x+1, y), (x, y+1) and (x+1, y+1). The box must start at (0, 0) and end at (n-2, m-2). At all moments, including the start and the end, all four cells occupied by the box must be empty (i.e., they may not contain any obstacles). At all moments, the whole box must be inside the board. In each step, we can only move the box up / down / left / right by one cell. That is, if we have the box at the position (x, y), we can move it to (x-1, y), (x+1, y), (x, y-1), or (x, y+1).
You are given the String[] board that describes the current state of the board: '#' is an obstacle, '.' is an empty cell. Find the minimal number of obstacles that have to be removed in order to create a board on which it is possible to move a 2x2 box from (0, 0) to (n-2, m-2) in the way described above.
Definition
- Class:
- TwoByTwo
- Method:
- minimal
- Parameters:
- String[]
- Returns:
- int
- Method signature:
- int minimal(String[] board)
- (be sure your method is public)
Notes
- The return value is always well-defined. In particular, note that if we remove all obstacles we will certainly have a valid board.
Constraints
- n, m will be between 2 and 16, inclusive.
- board will contain exactly n element.
- Each element in board will contain exactly m element.
- Each character in board will be '#' or '.'.
Examples
{"..#", "...", "#.."}Returns: 1
The optimal solution is to remove any one of these two obstacles. For example, if we remove the top-right one, we can move from top-left to bottom-right by moving right and then moving down: oo. .oo ... oo. -> .oo -> .oo #.. #.. #oo{"#..#.#", "##.##."}Returns: 7
This time we need to remove all of them.{"......", "......", "####..", "####..", "......", "......", "..####", "..####", "......", "......"}Returns: 0
This time we don't need to remove anything.{".###.#.#", "#.#.#..#", "#..#..#.", "#..#.#.#", "#.#....#", "#.##.##.", ".#.##...", "#.####.#"}Returns: 10
{"##", "##"}Returns: 4
Back to all problems