cho.sh

Bacteria

Rectangular colonies on a grid evolve each second by a north-and-west neighbor rule, and the task asks when every cell becomes empty.

Hard8Dynamic programmingMatrixNo attempts yetTime limit5sMemory limit512 MB

Problem

Bacteria live on an infinite grid of cells. A cell holds at most one bacterium.

Every second the following two changes happen at the same time.

  1. A bacterium whose north neighbor and west neighbor are both empty dies.
  2. An empty cell whose north neighbor and west neighbor both hold a bacterium gets a new bacterium.

At the start the grid holds a positive, finite number of bacteria, and the occupied cells form one or more rectangular regions.

Determine how many seconds pass before all the bacteria die.

The grid below starts with six bacteria and is empty after 6 seconds. A 1 is a cell with a bacterium and a 0 is an empty cell. The leftmost column is X = 1 and the top row is Y = 1.

t = 0      t = 1      t = 2      t = 3      t = 4      t = 5      t = 6
000010     000000     000000     000000     000000     000000     000000
011100     001110     000110     000010     000000     000000     000000
010000     011000     001100     000110     000010     000000     000000
010000     010000     011000     001100     000110     000010     000000
000000     000000     000000     000000     000000     000000     000000

Input

The first line contains CC, the number of test cases.

Each test case is then given in the following format.

  • One line containing RR, the number of rectangles of cells that initially contain bacteria.
  • RR lines containing four space-separated integers X1X_1 Y1Y_1 X2X_2 Y2Y_2. Every cell whose X coordinate is between X1X_1 and X2X_2 inclusive and whose Y coordinate is between Y1Y_1 and Y2Y_2 inclusive contains a bacterium.

The rectangles may overlap.

North is the direction of decreasing Y coordinate, and west is the direction of decreasing X coordinate.

Limits

  • 1≤C≤1001 \le C \le 100
  • 1≤R≤101 \le R \le 10
  • 1≤X1≤X2≤1001 \le X_1 \le X_2 \le 100
  • 1≤Y1≤Y2≤1001 \le Y_1 \le Y_2 \le 100
  • The number of cells initially containing bacteria is at most 1000000.

Output

For each test case, print one line in the form Case #N: T, where NN is the test case number starting from 1 and TT is the number of seconds until all the bacteria die.