#![allow(unused_imports)] #![allow(non_snake_case)] use std::cmp::*; use std::collections::*; use std::io::Write; #[allow(unused_macros)] macro_rules! debug { ($($e:expr),*) => { #[cfg(debug_assertions)] $({ let (e, mut err) = (stringify!($e), std::io::stderr()); writeln!(err, "{} = {:?}", e, $e).unwrap() })* }; } fn main() { let v = read_vec::(); let (h, w, k) = (v[0], v[1], v[2]); let mut grid = vec![]; for i in 0..h { let chs = read::() .chars() .map(|ch| ch.to_digit(36).unwrap() as usize - 10) .collect::>(); grid.push(chs); } let mut cum2d_vec = vec![CumulativeSum2D::new(w, h); 26]; for y in 0..h { for x in 0..w { cum2d_vec[grid[y][x]].add(x, y, 1); } } for ref mut cum2d in cum2d_vec.iter_mut() { cum2d.build(); } let criterion1 = |start_x: usize, start_y: usize, width: usize| -> bool { let mut found = 0; for ref cum2d in cum2d_vec.iter() { if cum2d.query(start_x, start_y, start_x + width, start_y + width) > 0 { found += 1; } if found > k { return false; } } found <= k }; let criterion2 = |start_x: usize, start_y: usize, width: usize| -> bool { let mut found = 0; for ref cum2d in cum2d_vec.iter() { if cum2d.query(start_x, start_y, start_x + width, start_y + width) > 0 { found += 1; } if found > k - 1 { return false; } } found <= k - 1 }; let mut ans = 0; for y in 0..h { for x in 0..w { let max_width = min(h - y, w - x); let (lb2, _) = binary_search(0, max_width + 1, x, y, criterion2); let (lb1, _) = binary_search(lb2, max_width + 1, x, y, criterion1); // debug!(x, y, lb1, lb2, max_width); ans += lb1 - lb2; } } println!("{}", ans); } fn read() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } fn read_vec() -> Vec { read::() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } #[derive(Clone)] struct CumulativeSum2D { data: Vec>, } impl CumulativeSum2D { fn new(w: usize, h: usize) -> CumulativeSum2D { CumulativeSum2D { data: vec![vec![0; w + 1]; h + 1], } } fn add(&mut self, mut x: usize, mut y: usize, z: i32) { x += 1; y += 1; if x >= self.data[0].len() || y >= self.data.len() { return; } self.data[y][x] += z; } fn build(&mut self) { for i in 1..self.data.len() { for j in 1..self.data[i].len() { self.data[i][j] += self.data[i][j - 1] + self.data[i - 1][j] - self.data[i - 1][j - 1]; } } } // sum of [sx, gx), [sy, gy) fn query(&self, sx: usize, sy: usize, gx: usize, gy: usize) -> i32 { self.data[gy][gx] - self.data[gy][sx] - self.data[sy][gx] + self.data[sy][sx] } } fn binary_search( lb: usize, ub: usize, start_x: usize, start_y: usize, criterion: F, ) -> (usize, usize) where F: Fn(usize, usize, usize) -> bool, { let mut ok = lb; let mut ng = ub; while ng - ok > 1 { let mid = (ng + ok) / 2; if criterion(start_x, start_y, mid) { ok = mid; } else { ng = mid; } } (ok, ng) }