Construct connected crop layout and safe paths

Problem A — Construct a garden with connected crop regions

You are given an N × M rectangular grid (a garden) that must be fully planted using k crop types labeled a, b, ..., k.

You are also given required counts for each crop: counts = [c1, c2, ..., ck] such that:

• c1 + c2 + ... + ck = N * M

Task

Construct and output any N × M grid assignment of crop labels such that:

1. Every cell is assigned exactly one crop.
2. Crop i appears exactly ci times.
3. For each crop type, all its cells form one connected component under 4-directional adjacency (up/down/left/right).

If it is impossible, output that it cannot be done.

Follow-up (non-rectangular garden)

Now the garden is the union of two squares:

• One square of size N × N
• One square of size M × M

They are stacked vertically with their left edges aligned, and they do not overlap. (So the overall shape may be non-rectangular if N ≠ M.)

You are given k crops with counts summing to N^2 + M^2.

Construct and output a planting for this shape such that each crop’s cells are 4-connected within the shape.

Problem B — Grid shortest path and maximize distance from a cat

You are given an N × N grid where:

• 0 = land (walkable)
• 1 = water (blocked)

You are also given two land cells:

• S = start
• T = target

Movement is allowed only on land cells and only in 4 directions.

Task 1

Find the shortest path from S to T (or the shortest path length). If no path exists, report failure.

Follow-up (maximize minimum Manhattan distance to a cat)

In addition, one cell contains a cat at position C (not necessarily on the path).

For any path P from S to T (moving only on land), define the path’s “safety” as:

$\text{safety}(P) = \min_{v \in P} \; \text{ManhattanDistance}(v, C)$

where Manhattan distance is |r1 - r2| + |c1 - c2|.

Find a path from S to T that maximizes this safety value (i.e., maximizes the minimum Manhattan distance to the cat among all cells on the path). If no path exists, report failure.

(You may return either the maximum achievable safety value, or the corresponding path.)