牛客算法周周练19 E 地、颜色、魔法
题目原意是
我的做法是循环矩阵,然后用岛问题的方法去感染,如果这个岛屿是边界岛就不被计数,否则就计数。然后遇到'#'也计数。
自己写了对数器,测试了5万次没问题,不知道oj为啥一直75过不去,难受!想了一晚上,不知道疏忽了什么。下面是失败的代码!
import java.io.*;
public class Main{
public static int[] dx = {-1,1,0,0};
public static int[] dy = {0,0,-1,1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] info = br.readLine().split(" ");
int length = Integer.parseInt(info[0]);
int width = Integer.parseInt(info[1]);
char[][] matrix = new char[length][width];
for (int i = 0; i < length; i++) {
char[] arr = br.readLine().toCharArray();
matrix[i] = arr;
}
System.out.println(method2(matrix));
}
public static int method2(char[][] matrix) {
if(matrix==null || matrix.length==0 || matrix[0].length==0) {
return 0;
}
int res = 0;
int length = matrix.length;
int width = matrix[0].length;
for (int i = 0; i < length; i++) {
for (int j = 0; j < width; j++) {
if (matrix[i][j] == '#') {
res++;
} else if (matrix[i][j] == '.') {
Island is = new Island(i, j, matrix);
res += is.flag ? is.size : 0;
}
}
}
return res;
}
public static class Island {
boolean flag;
int size;
public Island(int i, int j, char[][] matrix) {
flag = true;
size = 0;
infect(i, j, matrix);
}
public void infect(int i, int j, char[][] matrix) {
if (i = matrix.length || j >= matrix[0].length) {
flag = false;
return;
}
if (matrix[i][j] == '#') {
return;
}
if (matrix[i][j] == '.') {
size++;
matrix[i][j] = 'a';
infect(i - 1, j, matrix);
infect(i + 1, j, matrix);
infect(i, j - 1, matrix);
infect(i, j + 1, matrix);
}
}
}
}