AI Tetris (Large)

Dongi is a beginner game developer, and while studying programming he built his own Tetris. Tetris is played on a board of 20 rows and 10 columns. Block shapes come down from the top, and the player rotates them or moves them left and right to stack them. When a block can go down no further and stops where it is, every row that is completely filled with blocks is deleted, and the player gets 1 point per deleted row. The rows above keep their shape and come down. There are seven block shapes, and each one can also be rotated by 90, 180, or 270 degrees.

Figure: a 20 by 10 board (left) and the seven block shapes (right)

Dongi is slow with his hands, so past a certain difficulty he cannot clear the game himself. He added a cheat just for himself. The cheat works like this.

• The block Dongi is currently steering disappears.
• Dongi cannot steer the next block. It appears at the best position and takes the best path.
• Among all seven shapes and all of their rotations, the one that deletes the most rows is chosen automatically.
• Once a block appears, its shape never changes and it never rotates.

A block may appear at any position that fits entirely inside the top four rows, and those four rows are always empty. After it appears, it moves one cell at a time, down, left or right. It cannot enter a cell outside the board or a cell that already holds a block, and it cannot move up. It may step sideways in the middle of a descent, slip under an overhang, and then go down again. The block stops at a position where it cannot move down even one more cell.

Given the state of the board, write a program that computes the largest number of rows one use of the cheat can delete.

The board is given on 20 lines, one line per row. Each line is a string of length 10 made of 0 and 1, where 0 is an empty cell and 1 is a cell filled with a block.

The line given first is the top row of the board. The first four lines from the top are always all zeros.

Every row has at least one empty cell.

Print on one line the largest number of rows the cheat can delete.