Original proposer: admin

As in this problem, when you want to count how many distinct items there are, it is convenient to put all of them in a set and find the size.

Extract \(M\times M\) regions, and put them in a set.

Sample code (C++):

#include<bits/stdc++.h>
using namespace std;

int main(){
  int N,M;
  cin >> N >> M;
  vector<string>S(N);
  for(int i=0;i<N;i++)cin >> S[i];

  set<vector<string>>grid_set;
  for(int i=0;i<N-M+1;i++)for(int j=0;j<N-M+1;j++){
    vector<string>grid;
    for(int ii=i;ii<i+M;ii++)grid.push_back(S[ii].substr(j,M));
    grid_set.insert(grid);
  }

  cout << grid_set.size() << endl;
}

In Python, you cannot store a set in a list, so you need to use a tuple instead.

Sample code (Python)

N,M=map(int,input().split())
S=[input() for _ in range(N)]

grid_set=set()
for i in range(N-M+1):
  for j in range(N-M+1):
    grid = tuple(S[ii][j:j+M] for ii in range(i,i+M))
    grid_set.add(grid)

print(len(grid_set))