标题:欢乐的周末 | 时间限制:1秒 | 内存限制:262144K | 语言限制:不限 小华和小为是很要好的朋友,他们约定周末一起吃饭。通过手机交流,他们在地图上选择了多个聚餐地点(由于自然地形等原因,部分聚餐地点不可达),求小华和小为都能到达的聚餐地点有多少个? import java.util.*;public class Main{        /**    * 核心方法,计算最大可到达的点数目    */    private static int getRes(int[][] pos, int[][] arr) {        int result = 0;        // m,n最大只到100,所以这里以空间换时间。空间O(2*m*n)        boolean[][] map1 = new boolean[arr.length][arr[0].length];        boolean[][] map2 = new boolean[arr.length][arr[0].length];        // 对每个人开始外拓        expand(pos[0][0], pos[0][1], map1, arr);        expand(pos[1][0], pos[1][1], map2, arr);                // 统计3的位置两人都可达的点数        for (int i=0;i<arr.length;++i) {            for (int j=0;j<arr[0].length;++j) {                if (arr[i][j]==3 && map1[i][j] && map2[i][j]) {                    result++;                }            }        }        return result;    }        /**    * 从指定位置开始外拓,    */    private static void expand(int x, int y, boolean[][] map, int[][] arr) {        if (x<0 || x>=arr.length || y<0 || y>=arr[0].length || arr[x][y]==1) {            return;        }        // 已经描过点,不处理        if (map[x][y]) {            return;        }        map[x][y] = true;        // 依次从上下左右外拓        expand(x-1, y, map, arr);        expand(x+1, y, map, arr);        expand(x, y-1, map, arr);        expand(x, y+1, map, arr);    }        public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        // TODO 两个的顺序可能得是反的        int m = scanner.nextInt();        int n = scanner.nextInt();        int[][] arr = new int[m][n];        int[][] pos = new int[2][2];        int index = 0;        for (int i=0;i<m;++i) {            for (int j=0;j<n;++j) {                arr[i][j] = scanner.nextInt();                if (arr[i][j]==2) {                    pos[index][0] = i;                    pos[index][1] = j;                    index++;                }            }        }        System.out.println(getRes(pos, arr));    }}
点赞 0
评论 0
全部评论

相关推荐

中国外运吉布提 汽修售后店长 25K~30K/月
点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务