一个的只由小写英文字母组成的矩阵 ,牛牛想找到一个面积最小的正方形子矩阵满足该正方形子矩阵包含至少种不同的字母。
第一行输入三个正整数。
接下来 行每行输入一个长度为 的字符串,其中第 行第 个字母为 。
其中 为所有小写英文字母'a'-'z'的集合。
输出一个正整数表示包含至少 种不同字母的方形子矩阵的边长,如果不存在该子方阵,输出。
4 4 3 aabc aaaa axaz abcd
2
不存在边长为 的方形子矩阵包含至少 种不同的字母。
如图,存在边长为 的方形子矩阵包含至少 种不同的字母:
2 2 5 ab cd
-1
显然矩阵总共只有 种字符,因此答案为 。
import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] params = br.readLine().split(" "); int n = Integer.parseInt(params[0]); int m = Integer.parseInt(params[1]); int k = Integer.parseInt(params[2]); char[][] matrix = new char[n][]; for(int i = 0; i < n; i++){ matrix[i] = br.readLine().toCharArray(); } int resEdge = -1; for(int edge = Math.min(n, m); edge >= (int)Math.ceil(Math.sqrt(k)); edge--){ if(convolution(matrix, edge, k)){ resEdge = edge; }else{ break; } } System.out.println(resEdge); } private static boolean convolution(char[][] matrix, int edge, int lb){ // 从左上角初始化计数器 int[] counter = new int[26]; int nunique = 0; for(int i = 0; i < edge; i++){ for(int j = 0; j < edge; j++){ if(counter[matrix[i][j] - 'a'] == 0){ nunique++; } counter[matrix[i][j] - 'a']++; } } if(nunique >= lb){ return true; } // 之字形滑动窗口 boolean left2right = true; // 先从左往右滑动 for(int i = 0; i <= matrix.length - edge; i++){ if(left2right){ for(int j = 0; j <= matrix[0].length - edge; j++){ if(j > 0){ for(int r = i; r < i + edge; r++){ counter[matrix[r][j - 1] - 'a']--; if(counter[matrix[r][j - 1] - 'a'] == 0){ nunique--; } counter[matrix[r][j + edge - 1] - 'a']++; if(counter[matrix[r][j + edge - 1] - 'a'] == 1){ nunique++; } } } if(nunique >= lb){ return true; } } // 构建下一行的初始窗口 if(i + edge < matrix.length){ for(int k = matrix[0].length - edge; k < matrix[0].length; k++){ counter[matrix[i][k] - 'a']--; if(counter[matrix[i][k] - 'a'] == 0){ nunique--; } counter[matrix[i + edge][k] - 'a']++; if(counter[matrix[i + edge][k] - 'a'] == 1){ nunique++; } } } }else{ for(int j = matrix[0].length - edge; j >= 0; j--){ if(j < matrix[0].length - edge){ for(int k = i; k < i + edge; k++){ counter[matrix[k][j + edge] - 'a']--; if(counter[matrix[k][j + edge] - 'a'] == 0){ nunique--; } counter[matrix[k][j] - 'a']++; if(counter[matrix[k][j] - 'a'] == 1){ nunique++; } } } if(nunique >= lb){ return true; } } if(i + edge < matrix.length){ for(int k = 0; k < edge; k++){ counter[matrix[i][k] - 'a']--; if(counter[matrix[i][k] - 'a'] == 0){ nunique--; } counter[matrix[i + edge][k] - 'a']++; if(counter[matrix[i + edge][k] - 'a'] == 1){ nunique++; } } } } left2right = !left2right; } return false; } }