package chelper; import io.InputReader; import io.OutputWriter; import misc.GCJSolution; public class TaskA extends GCJSolution { private int n; private int m; private int cutsX; private int cutsY; private boolean[][] map; private int[][] ps; public void solve(int testNumber, InputReader in, OutputWriter out) { wrapSolve(testNumber, in, out); } int sum(int x0, int y0, int x1, int y1) { int res = ps[x1][y1]; if (x0 > 0) { res -= ps[x0 - 1][y1]; } if (y0 > 0) { res -= ps[x1][y0 - 1]; } if (x0 > 0 && y0 > 0) { res += ps[x0 - 1][y0 - 1]; } return res; } @Override public void solve(int testNumber) { n = in.nextInt(); m = in.nextInt(); cutsX = in.nextInt(); cutsY = in.nextInt(); map = new boolean[n][m]; for (int i = 0; i < n; i++) { String s = in.nextString(); for (int j = 0; j < m; j++) { map[i][j] = s.charAt(j) == '@'; } } ps = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (i > 0) { ps[i][j] += ps[i - 1][j]; } if (j > 0) { ps[i][j] += ps[i][j - 1]; } if (i > 0 && j > 0) { ps[i][j] -= ps[i - 1][j - 1]; } if (map[i][j]) { ps[i][j]++; } } } int[] cx0 = new int[cutsX + 1]; int[] cx1 = new int[cutsX + 1]; int[] cy0 = new int[cutsY + 1]; int[] cy1 = new int[cutsY + 1]; int total = sum(0, 0, n - 1, m - 1); int cutC = (cutsX + 1) * (cutsY + 1); if (total % cutC != 0) { out.println("IMPOSSIBLE"); return; } int perC = total / cutC; int cutStartX = 0; int cutStartY = 0; for (int i = 0; i < cutsX + 1; i++) { boolean ok = false; for (int cutEndX = cutStartX; cutEndX < n; cutEndX++) { int s = sum(cutStartX, 0, cutEndX, m - 1); if (s == perC * (cutsY + 1)) { cx0[i] = cutStartX; cx1[i] = cutEndX; cutStartX = cutEndX + 1; ok = true; break; } } if (!ok) { out.println("IMPOSSIBLE"); return; } } for (int i = 0; i < cutsY + 1; i++) { boolean ok = false; for (int cutEndY = cutStartY; cutEndY < m; cutEndY++) { int s = sum(0, cutStartY, n - 1, cutEndY); if (s == perC * (cutsX + 1)) { cy0[i] = cutStartY; cy1[i] = cutEndY; cutStartY = cutEndY + 1; ok = true; break; } } if (!ok) { out.println("IMPOSSIBLE"); return; } } for (int i = 0; i < cutsX + 1; i++) { for (int j = 0; j < cutsY + 1; j++) { int s = sum(cx0[i], cy0[j], cx1[i], cy1[j]); if (s != perC) { out.println("IMPOSSIBLE"); return; } } } out.println("POSSIBLE"); } }