Hide

Problem F
Jumping Spiders

/problems/jumpingspider/file/statement/en/img-0001.jpg

Jumping spiders are so-named because of their propensity to jump at prey. In this problem you are presented with the prints of what may be a jumping spider. If each print in a trail of prints is within 3 lengths (Manhattan distance) of 7 additional prints, they could be those of a jumping spider, because that would be consistent with the spider with all 8 feet on the ground. This is the main criteria. When walking (not jumping), the spider is able to pick up a foot and reach an additional 3 lengths before putting it down, thus we might also have a jumping spider if a print is within 3 lengths of another print that meets the first criteria of being within 3 lengths of 7 additional prints. This is the alternate criteria.

There may be gaps of greater than 3 lengths between separate trails of prints that may result if the spider was walking along and then jumped. If there are any prints that do not conform to these criteria, there may be something other than a jumping spider in the area, and you can remove them from consideration. Your task is to determine if all the prints can be accounted for as belonging to a jumping spider, and to give the minimum number of jumps the spider must have made.

In the sample figure note the orange area with 8 prints. 4 of them are within distance 3 of the other 7, so they would meet the main distance criteria. The other 4 are just 1 length away from at least one of the 4 so they meet the alternate criteria. No other prints around this set can be accounted for by either criteria, so we have identified one potential walking trail. The green and yellow areas likewise meet the two criteria for trails, so we have 3 trails in all which could have been created by one jumping spider making 2 jumps inside the sample area.

Input

The first line contains the number of $rows$ and $columns$ in the area $(1 \le rows,columns \le 25)$ The following $rows$ lines each contains $columns$ 0’s and 1’s where 0 indicates no print and 1 indicates the presence of a print at that location.

Output

Format as demonstrated. Report if there might be a jumping spider in the area, and if so, the minimum number of jumps he/she must have made. Report how many prints could not have been made by a jumping spider. In the illustrated sample, there could be a jumping spider making at least 2 jumps, and there are at least 2 prints made by something else.

Sample Input 1	Sample Output 1
18 17 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 1 0 1 1 1 0 1 0 0 0 0 0 0 0 1 1 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0	Yes 2 2

Sample Input 1

Sample Output 1

18  17
0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0
1 1 0 1 1 1 0 1 0 1 0 0 0 0 0 0 0
1 1 1 0 1 0 1 1 1 0 1 0 0 0 0 0 0
0 1 1 0 1 1 1 0 1 1 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0 0 0 1 0 1 0 0
0 0 0 1 1 0 1 0 0 0 0 0 1 1 1 0 0
0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0

Yes
2 
2

Sample Input 2	Sample Output 2
8 8 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1	No 0 8

Problem FJumping Spiders

Input

Output

Problem F
Jumping Spiders