package chelper; import java.util.ArrayList; import java.util.Arrays; import java.util.HashSet; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.Set; import io.InputReader; import io.OutputWriter; import misc.SimpleSavingChelperSolution; public class I extends SimpleSavingChelperSolution { public void solve(int testNumber, InputReader in, OutputWriter out) { wrapSolve(testNumber, in, out); } int[][] dirs = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, }; @Override public void solve(int testNumber) { int n = in.nextInt(); int m = in.nextInt(); long q = in.nextLong(); long p = in.nextLong(); long[][] starts = new long[n][m]; boolean[][] walls = new boolean[n][m]; for (int i = 0; i < n; i++) { String s = in.nextString(); for (int j = 0; j < m; j++) { char c = s.charAt(j); walls[i][j] = c == '*'; long k = c - 'A' + 1; if (k >= 1 && k <= 26) { starts[i][j] = k * q; } } } long[][] res = new long[n][m]; int[][] Q = new int[10000][2]; boolean[][] visited = new boolean[n][m]; for (int sx = 0; sx < n; sx++) { for (int sy = 0; sy < m; sy++) { // sx = 100; // sy = 100; if (starts[sx][sy] == 0) { continue; } int qs = 0; int ql = 0; long v = starts[sx][sy]; // long vt = ((long) sx) * m + sy; visited[sx][sy] = true; Q[ql][0] = sx; Q[ql++][1] = sy; res[sx][sy] += v; int waveSize = 1; v /= 2; while (waveSize != 0 && v > 0) { int nextWaveSize = 0; // out.println(waveSize + " " + ql + " " + v); for (int i = 0; i < waveSize; i++) { int x = Q[qs + i][0]; int y = Q[qs + i][1]; for (int ii = 0; ii < 4; ii++) { int xx = x + dirs[ii][0]; int yy = y + dirs[ii][1]; if (xx < 0 || yy < 0 || xx >= n || yy >= m || visited[xx][yy] || walls[xx][yy]) { continue; } res[xx][yy] += v; visited[xx][yy] = true; Q[ql][0] = xx; Q[ql++][1] = yy; nextWaveSize++; } } qs += waveSize; waveSize = nextWaveSize; v /= 2; } for (int i = 0; i < ql; i++) { visited[Q[i][0]][Q[i][1]] = false; } // return; } } // for (int letter = 0; letter < 26; letter++) { // if (starts[letter][0] == -1) { // continue; // } // // long v = (letter + 1) * q; // // List next = new ArrayList<>(); // next.add(starts[letter]); // // boolean[][] visited = new boolean[n][m]; // // while (!next.isEmpty()) { // List nnext = new ArrayList<>(); // for (int[] ints : next) { // int x = ints[0]; // int y = ints[1]; // // visited[x][y] = true; // res[x][y] += v; // // for (int[] dir : dirs) { // int xx = x + dir[0]; // int yy = y + dir[1]; // // if (xx < 0 || yy < 0 || xx >= n || yy >= m || visited[xx][yy]) { // continue; // } // // nnext.add(new int[]{xx, yy}); // } // } // // next = nnext; // v /= 2; // } // for (int i = 0; i < n; i++) { // for (int j = 0; j < m; j++) { // out.print(res[i][j] + " "); // } // out.println(); // } int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (res[i][j] > p) { ans++; } } } out.println(ans); } }