Down town BigCity is covered by a grid of n East-West avenues (numbered from 1 to n) intersecting
with n North-South streets (numbered from 1 to n). At the intersection between an avenue and a street,
there is a light post. At each avenue or street, there is a power switch which turns on all n lights along that
avenue/street. At day time, all the lights are automatically turned off. Every evening, due to security
reasons, the lights at a certain number of intersections must be turned on. To minimize the effort to turn on
the required lights, they wish to use the smallest number of power switches.
Your goal is to write a program that computes the smallest number of power switches that must be used
to turn on the required lights.
The input file consists of several data sets. The first line of the input file contains the number of data
sets which is a positive integer and is not bigger than 200. The following lines describe the data sets.
For each data set, the first line contains an integer n (1 ≤ n ≤ 30). Next n lines (each of which contains n
binary digits separated by space) contains a matrix R of size n×n representing the requirements about the
lights which need to be turned on. The value 1 of R(i,j) means that the light at the intersection between ith
avenue and jth street must be turned on. The value 0 of R(i,j) means that there is no requirement for the
light at the intersection between ith avenue and jth street.
For each data set, write in one line an integer representing the smallest number of power switches that
must be turned on.
1 7 0 0 1 1 0 1 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 0 1 1 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1
5
Migrated from old NTUJ.
The ACM-ICPC 2010 Asia Regional Contest, Site Hanoi
| No. | Testdata Range | Score |
|---|