Contest1329/H.java

package tuirngCup2019ahstuACM;

import java.util.*;
import java.util.List;
/*
dfs代码会有运行错误，我觉得可能是因为数据量过大，引起栈溢出，导致运行错误
 */
public class H {
    private static class Result implements Comparable<Result>{
        int s, c;
        Result(int s, int c){
            this.s = s;
            this.c = c;
        }

        @Override
        public int compareTo(Result o) {
            if (s != o.s)return Integer.compare(o.s, s);//面积从大到小排序
            return Integer.compare(c, o.c);//周长从大到小排序
        }
    }
    private static boolean[][] vis, book;//vis用来优化点不要重复访问，book作为dfs的递归过程的标记数组
    private static char[][] iceCream;
    private static int[][] next = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    private static int s, c, n;
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        n = cin.nextInt();
        iceCream = new char[n][n];
        vis = new boolean[n][n];
        for (int i = 0; i < n; i++){
            char[] row = cin.next().toCharArray();
            for(int j = 0; j < n; j++){
                iceCream[i][j] = row[j];
            }
        }
        List<Result>res = new ArrayList<>();
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(iceCream[i][j] == '#' && !vis[i][j]){
                    book = new boolean[n][n];
                    s = 0; c = 0;
                    dfs(i, j);
                    res.add(new Result(s,c));
                }
            }
        }
        Collections.sort(res);
        System.out.println(res.get(0).s + " " + res.get(0).c);
    }

    private static void dfs(int x0, int y0) {
        if (!vis[x0][y0]) {
            vis[x0][y0] = true;
            s++;
            c += icecreamBoundary(x0, y0);
        }
        for(int i = 0; i < 4; i++){
            int x = x0 + next[i][0];
            int y = y0 + next[i][1];
            if(x < 0 || y < 0 || x >= n || y >= n || iceCream[x][y] == '.' || book[x][y]){
                continue;
            }
            book[x][y] = true;
            dfs(x, y);
            book[x][y] = false;
        }
    }

    private static int icecreamBoundary(int x0, int y0) {
        int ret = 0;
        for(int i = 0; i < 4; i++){
            int x = x0 + next[i][0];
            int y = y0 + next[i][1];
            if(x < 0 || y < 0 || x >= n || y >= n || iceCream[x][y] == '.'){
                ret++;
            }
        }
        return ret;
    }
}