题目描述
blablabla
样例
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static int n;
public static int ans = 0;
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(in.readLine());
int[][] first = new int[n][n];
int[][] second = new int[n][n];
// 两个矩阵读取
for (int time = 0; time < 2; time++) {
for (int i = 0; i < n; i++) {
String[] s = in.readLine().split(" ");
for (int j = 0; j < n; j++) {
if (time == 0) {
first[i][j] = Integer.parseInt(s[j]);
} else {
second[i][j] = Integer.parseInt(s[j]);
}
}
}
}
int[][] re90 = Revolve(1, second);
int[][] re180 = Revolve(2, second);
int[][] re270 = Revolve(3, second);
int[][] re90f = Revolve(1, first);
int[][] re180f = Revolve(2, first);
int[][] re270f = Revolve(3, first);
//枚举旋转,以及和四边位置拼接+
getRight(first,second);getDown(first,second);getLeft(first,second);getTop(first,second);
getRight(first,re90);getDown(first,re90);getLeft(first,re90);getTop(first,re90);
getRight(first,re180);getDown(first,re180);getLeft(first,re180);getTop(first,re180);
getRight(first,re270);getDown(first,re270);getLeft(first,re270);getTop(first,re270);
getRight(re90f,second);getDown(re90f,second);getLeft(re90f,second);getTop(re90f,second);
getRight(re90f,re90);getDown(re90f,re90);getLeft(re90f,re90);getTop(re90f,re90);
getRight(re90f,re180);getDown(re90f,re180);getLeft(re90f,re180);getTop(re90f,re180);
getRight(re90f,re270);getDown(re90f,re270);getLeft(re90f,re270);getTop(re90f,re270);
getRight(re180f,second);getDown(re180f,second);getLeft(re180f,second);getTop(re180f,second);
getRight(re180f,re90);getDown(re180f,re90);getLeft(re180f,re90);getTop(re180f,re90);
getRight(re180f,re180);getDown(re180f,re180);getLeft(re180f,re180);getTop(re180f,re180);
getRight(re180f,re270);getDown(re180f,re270);getLeft(re180f,re270);getTop(re180f,re270);
getRight(re270f,second);getDown(re270f,second);getLeft(re270f,second);getTop(re270f,second);
getRight(re270f,re90);getDown(re270f,re90);getLeft(re270f,re90);getTop(re270f,re90);
getRight(re270f,re180);getDown(re270f,re180);getLeft(re270f,re180);getTop(re270f,re180);
getRight(re270f,re270);getDown(re270f,re270);getLeft(re270f,re270);getTop(re270f,re270);
getTop(first,re270);
System.out.println(ans);
}
public static void getLeft(int[][] first, int[][] second) {
int[][] helper = new int[3 * n][3 * n];
// 旋转测试
for (int i = n, a = 0; i < 2 * n && a < n; i++, a++) {
for (int j = n, b = 0; j < 2 * n && b < n; j++, b++) {
helper[i][j] = first[a][b];
}
}
int time = 0;
while (time < 2 * n - 1) {
for (int i = 1 + time, a = 0; i < 2 * n + time && a < n; i++, a++) {
for (int j = 0, b = 0; j < 2 * n && b < n; j++, b++) {
helper[i][j] = second[a][b];
}
}
for(int i = 0;i < helper.length;i++) { for(int j = 0;j < helper.length;j++) {
if(helper[i][j] == 1) { ans =Math.max(ans, dfs(helper,i,j)); } } }
for (int i = 1 + time, a = 0; i < 2 * n + time && a < n; i++, a++) {
for (int j = 0, b = 0; j < 2 * n && b < n; j++, b++) {
helper[i][j] = 0;
}
}
time++;
}
}
public static void getDown(int[][] first, int[][] second) {
int[][] helper = new int[3 * n][3 * n];
// 旋转测试
int time = 0;
while (time < 2 * n - 1) {
for (int i = n, a = 0; i < 2 * n && a < n; i++, a++) {
for (int j = n, b = 0; j < 2 * n && b < n; j++, b++) {
helper[i][j] = first[a][b];
}
}
for (int i = 2 * n, d = 0; i < 3 * n && d < n; i++, d++) {
for (int j = 1 + time, k = 0; j < 2 * n + time && k < n; j++, k++) {
helper[i][j] = second[d][k];
}
}
// 搜
for (int i = 0; i < helper.length; i++) {
for (int j = 0; j < helper.length; j++) {
if (helper[i][j] == 1) {
ans = Math.max(ans, dfs(helper, i, j));
}
}
}
for (int i = 2 * n, d = 0; i < 3 * n && d < n; i++, d++) {
for (int j = 1 + time, k = 0; j < 2 * n + time && k < n; j++, k++) {
helper[i][j] = 0;
}
}
time++;
}
}
public static void getRight(int[][] first, int[][] second) {
int[][] helper = new int[3 * n][3 * n];
int time = 0;
while (time <2 * n - 1) {
for (int i = n, a = 0; i < 2 * n && a < n; i++, a++) {
for (int j = n, b = 0; j < 2 * n && b < n; j++, b++) {
helper[i][j] = first[a][b];
}
}
for (int i = 1 + time, d = 0; i < 2 * n + time && d < n; i++, d++) {
for (int j = 2 * n, k = 0; j <3 * n && k < n; j++, k++) {
helper[i][j] = second[d][k];
}
}
// 搜
for (int i = 0; i < helper.length; i++) {
for (int j = 0; j < helper.length; j++) {
if (helper[i][j] == 1) {
ans = Math.max(ans, dfs(helper, i, j));
}
}
}
for (int i = 1 + time, d = 0; i < 2 * n + time && d < n; i++, d++) {
for (int j = 2 * n, k = 0; j <3 * n && k < n; j++, k++) {
helper[i][j] = 0;
}
}
time++;
}
}
public static void getTop(int[][] first, int[][] second) {
int[][] helper = new int[3 * n][3 * n];
int time = 0;
while (time <2* n - 1) {
for (int i = n, a = 0; i < 2 * n && a < n; i++, a++) {
for (int j = n, b = 0; j < 2 * n && b < n; j++, b++) {
helper[i][j] = first[a][b];
}
}
for (int i = 0, d = 0; i < n && d < n; i++, d++) {
for (int j = 1+time, k = 0; j < 2 * n + time && k < n; j++, k++) {
helper[i][j] = second[d][k];
}
}
for (int i = 0; i < helper.length; i++) {
for (int j = 0; j < helper.length; j++) {
if (helper[i][j] == 1) {
ans = Math.max(ans, dfs(helper, i, j));
}
}
}
for (int i = 0, d = 0; i < n && d < n; i++, d++) {
for (int j = 1+time, k = 0; j < 2 * n + time && k < n; j++, k++) {
helper[i][j] = 0;
}
}
time++;
}
}
public static int dfs(int[][] helper, int i, int j) {
if (i < 0 || i >= helper.length || j < 0 || j >= helper.length) {
return 0;
}
// 海水返回0
if (helper[i][j] == 0) {
return 0;
}
// 此时剩下的情况为不是海水
helper[i][j] = 0;
// 搜四个方向并且搜到的+1
return dfs(helper, i + 1, j) + dfs(helper, i - 1, j) + dfs(helper, i, j + 1) + dfs(helper, i, j - 1) + 1;
}
// i: 1代表旋转90度,2代表旋转180度,3代表旋转270度
public static int[][] Revolve(int t, int[][] arr) {
int n = arr.length;
int[][] help = new int[n][n];
// 旋转90度
if (t == 1) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
help[i][j] = arr[n - 1 - j][i];
}
}
// 180度
} else if (t == 2) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
help[i][j] = arr[n - 1 - i][n - 1 - j];
}
}
} else {
// 270度
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
help[i][j] = arr[j][n - 1 - i];
}
}
}
return help;
}
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla