148 lines
2.9 KiB
Java
148 lines
2.9 KiB
Java
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");
|
|
}
|
|
}
|