题目原意是
我的做法是循环矩阵,然后用岛问题的方法去感染,如果这个岛屿是边界岛就不被计数,否则就计数。然后遇到'#'也计数。
自己写了对数器,测试了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); } } } }
全部评论
(0) 回帖