PROBLEM LINK:
Author: Devanshu Agarwal
Tester: Teja Vardhan Reddy
Editorialist: Hussain Kara Fallah
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Breadth First Search, Graph Theory
PROBLEM:
You are given a 1×1×2 bar (a cuboid) and a grid A with N rows (numbered 1 through N) and M columns (numbered 1 through M). Let’s denote the cell in row r and column c by (r,c).
Some cells of the grid are blocked, the remaining cells are free. Each cell has dimensions 1×1, the same as two opposite faces of the cuboid. When the bar is placed on the grid in such a way that one of its two 1×1 faces fully covers a cell (r,c), we say that the bar is standing on the cell (r,c). Initially, the bar is standing on a cell (x,y).
When the bar is placed on the grid, one of its faces is touching the grid; this face is called the base. In one move, you must roll the bar over one of its base edges (sides of the base); this base edge does not move and the bar is rotated 90∘ around it in such a way that it is still lying on the grid, but with a different base. In different moves, the bar may be rotated around different edges in different directions. After each move, the base of the bar must lie fully inside the grid and it must not cover any blocked cells. An example sequence of moves is shown here.
For each cell of the grid, determine the minimum number of moves necessary to achieve the state where the bar is standing on this cell or determine that it is impossible to achieve.
N,M \leq 1000
Explanation:
This is an adequate BFS problem. We care about 2 factors in our graph, the cell which our cuboid is standing on and the cuboid’s state which can be one of three.
- standing (denote it by 0)
- lying horizontally (denote it by 1)
- lying vertically (denote it by 2)
So nodes of our graph are tuples (row,col,state) whereas state can be (0,1,2). Our starting vertex is (startRow,startCol,0).
When representing some tuple where the cuboid is lying horizontally let (x,y) present the leftmost cell (as it’s covering 2 cells).
When representing some tuple where the cuboid is lying vertically let (x,y) present the upper cell (as it’s covering 2 cells).
I will describe edges in this graph briefly.
Edges from Nodes (r,c,0):
By rolling the bar to the right it moves to (r,c+1,1)
By rolling the bar to the left it moves to (r,c-2,1)
By rolling the bar up it moves to (r-2,c,2)
By rolling the bar down it moves to (r+1,c,2)
Edges from Nodes (r,c,1):
By rolling the bar to the right it moves to (r,c+2,0)
By rolling the bar to the left it moves to (r,c-1,0)
By rolling the bar up it moves to (r-1,c,1)
By rolling the bar down it moves to (r+1,c,1)
Edges from Nodes (r,c,2):
By rolling the bar to the right it moves to (r,c+1,2)
By rolling the bar to the left it moves to (r,c-1,2)
By rolling the bar up it moves to (r-1,c,0)
By rolling the bar down it moves to (r+2,c,0)
The rest is applying BFS algorithm.
Also before moving our cuboid, we must check the cells we are moving two if they are empty or not.
Complexity: O(N*M)
