题目描述
blablabla
样例
blablabla
算法1
(暴力枚举)
直接查两个矩阵最大长度,骗一半分 5/10
时间复杂度
参考文献
C++ 代码
package blueBridge.Test14;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Scanner;
public class t5 {
static int n;
static boolean vis1[][];
static boolean vis2[][];
public static void main(String[] args) throws IOException {
BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(sc.readLine());
int[][] map1 = new int[n][n];
int[][] map2 = new int[n][n];
vis1 = new boolean[n][n];
vis2 = new boolean[n][n];
for (int i = 0; i < n; i++) {
String[] s = sc.readLine().split(" ");
for (int j = 0; j < n; j++) {
map1[i][j] = Integer.parseInt(s[j]);
}
}
for (int i = 0; i < n; i++) {
String[] s = sc.readLine().split(" ");
for (int j = 0; j < n; j++) {
map2[i][j] = Integer.parseInt(s[j]);
}
}
int max1 = Integer.MIN_VALUE,max2 = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map1[i][j]!=0 && !vis1[i][j]){
max1 = Math.max(bfs1(i, j, map1),max1);
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map2[i][j]!=0 && !vis2[i][j]){
max2 = Math.max(bfs2(i, j, map2),max2);
}
}
}
System.out.println(max1+max2);
}
static int dx[] = {0,-1,0,1},dy[] = {-1,0,1,0};
static int bfs1(int x,int y,int[][] map) {
LinkedList<Node> nodes = new LinkedList<>();
nodes.offer(new Node(x,y));
vis1[x][y] = true;
int res = 1;
while (!nodes.isEmpty()) {
Node node = nodes.poll();
for (int i = 0; i < 4; i++) {
int xx = node.x + dx[i];
int yy = node.y + dy[i];
if (xx >= 0 && xx < n && yy >= 0 && yy < n && map[xx][yy] == 1 && !vis1[xx][yy]) {
vis1[xx][yy] = true;
nodes.offer(new Node(xx,yy));
res++;
}
}
}
return res;
}
static int bfs2(int x,int y,int[][] map) {
LinkedList<Node> nodes = new LinkedList<>();
nodes.offer(new Node(x,y));
vis2[x][y] = true;
int res = 1;
while (!nodes.isEmpty()) {
Node node = nodes.poll();
for (int i = 0; i < 4; i++) {
int xx = node.x + dx[i];
int yy = node.y + dy[i];
if (xx >= 0 && xx < n && yy >= 0 && yy < n && map[xx][yy] == 1 && !vis2[xx][yy]) {
vis2[xx][yy] = true;
nodes.offer(new Node(xx,yy));
res++;
}
}
}
return res;
}
static class Node{
int x,y;
public Node(int x,int y) {
this.x = x;
this.y = y;
}
}
}