JUMPPY - Jumppy and the Grid
Jumppy likes to jump! One day Jumppy went to a park. Jumppy can jump all over the park. The park can be thought of as a square grid with square cells of side length 1. The contents of the grid is either 0 (zero) or X. There are certain things which Jumppy likes. They are:
- Jumppy likes rectangles.
- Jumppy likes X.
Therefore Jumppy will jump only in the rectangles consisting of X. A rectangle is defined as follows:
- The whole rectangular region should contain only X.
- The rectangle should be surrounded with 0 or the boundary of the grid.
- The diagonally adjacent cell (see the definition) of the corner of the rectangle may be X or 0. (Refer to the first example).
Diagonally adjacent cell: Suppose the given cell has coordinates (p, q) then its diagonally adjacent cells would have coordinates (p+1, q+1), (p+1, q-1), (p-1, q+1), (p-1, q-1).
Now Jumppy is curious how many rectangles are there in the park. Help Jumppy find the number of rectangle.
Input
An integer n denoting the size of the grid. Then n lines follow each containing a string of n characters describing the square grid. All the characters will be either 0 or X.
Output
Output the number of rectangles in the given grid.
Constraints
0 < n <= 1000
Examples:
Input: 4 XX00 XX00 00XX 00XX Output: 2
Input: 5 00000 0XXX0 0XXX0 0XXX0 00X00 Output: 0
Input: 5 00000 0XXX0 0X0X0 0XXX0 00000 Output: 0
Input: 3 X0X 0X0 X0X Output: 5
Explanation
Case 1: As can be seen there are two rectangles as highlighted.
Case 2: The grid contains no rectangles because it violates the second condition of the definition.
Case 3: The grid contains no rectangles because it violates the first condition of the definition.
Case 4: The individual X in this case can be considered as rectangles.
hide comments
hodobox:
2016-02-06 21:18:51
Didn't experience any problems here, and O(n^2) without optimizing constants passed in 0.19 |
|
Rishav Goyal:
2015-07-29 20:41:19
@author : after trying hard on this problem, i was getting run time error. then i tried to upload one AC code of my friend , its giving Runtime error. Either something is wrong on spoj or input files. author u can verify what i said. |
|
:D:
2015-01-29 20:35:40
I don't know if time limit was changes, but currently O(N^2) with getchar map reading and O(N) memory complexity easily passes. |
|
newbie:
2014-11-08 17:34:44
time limit strict for O(n^2) to pass |
|
mehmetin:
2014-11-08 17:34:44
O(n^2) works fine without fast io. |
|
Akhilesh Anandh:
2014-11-08 17:34:44
Time limit too strict. O(n^2) algorithm is giving TLE even with fast IO. (Note that reading in the input itself is O(n^2), so you can't do better than that.)
|
Added by: | Anant Kumar |
Date: | 2014-11-03 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |