A higher resolution is required to access the IDE
- 41
Learning Opportunities
This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.
Statement
Goal
This puzzle is part of a multi-part Algorithm X tutorial and is meant to be done per the guidance in the following playground:Task:
Given a grid of numbers, find all rectangles that cover each positive number without covering other positive numbers. Each rectangle must have an area equal to the number it covers.
Input
Line 1: The width and height of the grid, space separated.
Next h lines: w space-separated integers. (0 s indicate blank cells)
Next h lines: w space-separated integers. (
Output
Navigating the grid from left to right and from top to bottom, for each positive number n, if there is at least one rectangle of area n which covers n without covering other positive numbers (we’ll call each a good rectangle), output the following:
Line 1: Three space separated integers: row col n, where row and col are the location of n on the grid.
Next 1 or more lines: Four space separated integers: r c width height for each good rectangle. r and c indicate the rectangle's top left corner. width and height indicate the rectangle's dimensions. These lines must be sorted by r, then c and then width.
Note: For output purposes, rows and columns must be zero-indexed. The top-left corner of each grid is row 0, col 0.
Line 1: Three space separated integers: row col n, where row and col are the location of n on the grid.
Next 1 or more lines: Four space separated integers: r c width height for each good rectangle. r and c indicate the rectangle's top left corner. width and height indicate the rectangle's dimensions. These lines must be sorted by r, then c and then width.
Note: For output purposes, rows and columns must be zero-indexed. The top-left corner of each grid is row 0, col 0.
Constraints
2 ≤ w, h ≤ 30
Example
Input
3 2 0 0 0 0 4 0
Output
1 1 4 0 0 2 2 0 1 2 2
A higher resolution is required to access the IDE