Under construction

Still being built. Things may change

Moving Marbles

Time limit0.5sMemory limit1024 MB

Summary
Given start and target 0/1 grids, find the fewest moves to reach the target by sliding, removing, or placing marbles. Print -1 if impossible.
Level

Medium7 of 10

Topics
Graph, Shortest path
Solved
No attempts yet

Moving Marbles

Hanseo has a board with HH rows and WW columns. Each cell may hold a marble, shown as 1 if the cell has a marble and 0 if it is empty. Given the initial state of the board, Hanseo wants to rearrange the marbles into a target pattern. Moving marbles is tedious for him, so he wants to use as few moves as possible.

In one move, Hanseo can do one of the following three actions.

  1. Move a marble to one of the 4 adjacent empty cells (up, down, left, right). A marble cannot be moved outside the board.
  2. Remove a marble from a cell of his choice and store it. There is no limit on how many marbles he can store, but when the target pattern is complete, he must have no stored marbles left.
  3. Place one of the stored marbles on an empty cell of his choice.

If the target pattern cannot be completed, print -1. Otherwise, print the minimum number of moves needed to complete it.

Examples4

  1. Example 1

    Input
    4 3
0 0 0 0
0 1 0 0
1 0 0 0
0 0 0 1
0 0 0 0
0 0 0 1
    Expected output
    4

  2. Example 2

    Input
    3 3
1 1 0
0 0 1
1 1 0
0 0 1
1 1 0
0 0 1
    Expected output
    -1

  3. Example 3

    Input
    2 2
1 1
0 0
1 1
0 0
    Expected output
    0

  4. Example 4

    Input
    4 4
0 0 1 0
1 1 0 0
0 0 0 0
0 0 0 1
1 0 0 0
0 0 0 0
1 1 0 0
0 0 1 0
    Expected output
    5