KOPC12F - K12-Counting Staircases
You are given a NxN matrix of 0's and 1's. A staircase is defined as a structure similar to the one given below filled with 1s.
Image Link : http://img546.imageshack.us/img546/7141/staircase.png
You are required to find the number of staircases of all heights greater than one in the given matrix. Since the answer can be very large, output the answer mod 106 + 3.
Input
The first line of the input file contains T which denotes the number of test cases.The first line of each test case contains an integer N.Then N lines follow for each test case where each of the lines contain N elements of the input array [NxN matrix].
T<=20 && N<=500;
Output
The output should contain T lines each line with the answer for each case.Print the answer modulo 10^6+3
Warning: Huge I/O
Example
Input:
2 3 1 1 1 1 1 1 1 1 1 2 1 0 1 1 Output:
5 1
hide comments
[Rampage] Blue.Mary:
2013-07-19 19:36:44
This problem will be hidden until the broken image is fixed. (i.e The author should make the picture SPOJ content rather than a link to other sites.) |
Added by: | Radhakrishnan Venkataramani |
Date: | 2012-01-31 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |