1221. Malevich Strikes Back!
2107 ワード
すいもんを繰り出す
import java.util.*;
import java.math.*;
public class Main {
public static void main(String[] args) {
int n;
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
n = in.nextInt();
if (n == 0) {
break;
}
int num0[][] = new int[n + 1][n + 1];// 0
int num1[][] = new int[n + 1][n + 1];// 1
int a[][] = new int[n + 1][n + 1];
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
a[i][j] = in.nextInt();
}
}
for (int j = 1; j <= n; ++j) {
num0[0][j] = num1[0][j] = 0;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (a[i][j] == 0) {
num1[i][j] = num1[i - 1][j];
num0[i][j] = num0[i - 1][j] + 1;
} else {
num1[i][j] = num1[i - 1][j] + 1;
num0[i][j] = 0;
}
}
}
int ans = -1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
int temp = num0[i][j];
if (temp > 1 && temp % 2 == 1) {
if (j + temp / 2 > n || j - temp / 2 < 1) {
continue;
}
// System.out.println(i+" "+j+" "+temp);
boolean yes = true;
int pre = temp;
for (int k = 1; k <= temp / 2; ++k) {
// System.out.println(pre);
if (!(num0[i - k][j + k] + 2 == pre && num1[i][j
+ k]
- num1[i - temp][j + k] == temp
- num0[i - k][j + k])) {
yes = false;
// System.out.println(k);
// System.out.println((num0[i-k][j+k])+" "+pre);
}
if (!(num0[i - k][j - k] + 2 == pre && num1[i][j
- k]
- num1[i - temp][j - k] == temp
- num0[i - k][j - k])) {
yes = false;
}
pre = pre - 2;
}
if (yes == true && temp > ans) {
ans = temp;
}
}
}
}
if (ans == -1) {
System.out.println("No solution");
} else {
System.out.println(ans);
}
}
}
}