You are analyzing a communication grid of size N (up to 18).
An N by N matrix of booleans describing the grid:
element (i, j) = 1 <=> node i and j can communicate with each other
Assuming a node cannot communicate with 2 or more nodes at the same time, describe an algorithm that return the maximum number of communicating nodes at any one time.
Submit this problem in the judge as "Q23"
There will be multiple test cases. The first line will contain an integer
numCase equal to the number of test cases.
For each test case, the there will be a line containing one integer N
N is described above.
N lines then follow, each with N characters of 0 or 1 that describes the matrix above.
The matrix will of course be symmetric.
For each test case, output the maximum number of communicating nodes at any one time.
3 5 01111 10000 10000 10000 10000 5 01111 10000 10001 10001 10110 18 001111111111111111 001111111111111111 110000000000000000 110000000000000000 110000000000000000 110000000000000000 110000000000000000 110000000000000000 110000000000000000 110000000000000000 110000000000000000 110000000000000000 110000000000000000 110000000000000000 110000000000000000 110000000000000000 110000000000000000 110000000000000000
2 4 4