竞赛讨论区 > 牛客算法周周练19 E 地、颜色、魔法
头像
风尽起长歌
发布于 2020-08-12 10:46
+ 关注

牛客算法周周练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);
            }
        }
    }
}

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐