Subsquares in a matrix P77893


Statement
 

pdf   zip

thehtml

Given an n × m matrix of numbers between 1 and 9, compute how many subsquares 3 × 3 it has with all the numbers between 1 and 9.

Input

Input consists of several cases. Every case begins with n and m, followed by an n × m matrix of integer numbers between 1 and 9. Suppose that n and m are between 3 and 100.

Output

For every matrix, print the number of subsquares 3 × 3 that have all the numbers between 1 and 9.

Public test cases
  • Input

    3 4
    1 2 3 4
    5 6 7 8
    9 8 4 8
    
    3 3
    1 1 1
    1 1 1
    1 1 1
    
    4 4
    1 2 3 7
    4 5 6 4
    7 8 9 1
    1 2 3 7
    

    Output

    1
    0
    4
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++ Python