扫描透镜——网易校招编程题

网易2016校招第三题


题目: 在NxM的草地上,提莫种了K个蘑菇,蘑菇爆炸的威力极大,兰博不想贸然去闯,而且蘑菇是隐形的。只有一种叫做扫描透镜的物品可以扫描出隐形的蘑菇,于是他回了一趟战争学院,买了2个扫描透镜,一个 扫描透镜可以扫描出(3x3)方格中所有的蘑菇,然后兰博就可以清理掉一些隐形的蘑菇。 问:兰博最多可以清理多少个蘑菇? 注意:每个方格被扫描一次只能清除掉一个蘑菇。

输入描述: 第一行三个整数:N,M,K,(1≤N,M≤20,K≤100),N,M代表了草地的大小;接下来K行,每行两个整数x,y(1≤x≤N,1≤y≤M)。代表(x,y)处提莫种了一个蘑菇。一个方格可以种无穷个蘑菇。

输出描述: 输出一行,在这一行输出一个整数,代表兰博最多可以清理多少个蘑菇。

解题思路:兰博有两个扫描透镜,要清理出最多的蘑菇,应该是先拿一个扫描透镜(3x3的框)扫描整个NxM草地,扫描过程分为两步:

  • 确定区域,统计该区域的个数。
  • 统计扫描到的最大值。 第一次扫描完,进行清除。接着进行第二次扫描,步骤同上。最后把两次扫描的结果加起来即可得到扫描出的最多的蘑菇数。

代码如下:

import java.util.Scanner;

public class ScanGlass {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int k = sc.nextInt();
            int[][] arr = new int[n][m];
            for (int i = 0; i < k; i++) {
                int x = sc.nextInt() - 1;
                int y = sc.nextInt() - 1;
                if (x < n && y < m) {
                    arr[x][y]++;
                }
            }
            Point firstPoint = findMaxNum(n, m, arr); // 第一次扫描到的最多蘑菇的区域
            clear(firstPoint, arr, n, m); // 清除第一次扫描过的蘑菇
            Point secondPoint = findMaxNum(n, m, arr); // 第二次扫描到的最多蘑菇的区域
            System.out.println(firstPoint.count + secondPoint.count);
        }
    }

    // 统计扫描到蘑菇的最大值
    private static Point findMaxNum(int n, int m, int[][] arr) {
        Point point = new ScanGlass().new Point();
        point.x = 0;
        point.y = 0;
        point.count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                Point tempPoint = getNumInLocation(n, m, arr, i, j);
                if (point.count < tempPoint.count) {
                    point = tempPoint;
                }
            }
        }
        return point;
    }

    private static Point getNumInLocation(int n, int m, int[][] arr,
            int startX, int startY) {
        // 确定扫描镜的区域
        int endX;
        int endY;
        if (startX + 2 > n - 1) {
            endX = n - 1;
        } else {
            endX = startX + 2;
        }
        if (startY + 2 > m - 1) {
            endY = m -1;
        } else {
            endY = startY + 2;
        }
        // 统计该区域的蘑菇个数
        Point point = new ScanGlass().new Point();
        point.count = 0;
        point.x = startX;
        point.y = startY;
        point.endX = endX;
        point.endY = endY;

        for (int i = startX; i <= endX; i++) {
            for (int j = startY; j <= endY; j++) {
                if (arr[i][j] > 0) {
                    point.count++;
                }
            }
        }
        return point;
    }

    // 删除第一次扫描过的蘑菇
    private static void clear(Point point, int[][] arr, int n, int m) {
        for (int i = point.x; i <= point.endX; i++) {
            for (int j = point.y; j <= point.endY; j++) {
                if (arr[i][j] > 0 && i < n & j < m) {
                    arr[i][j]--;
                }
            }
        }
    }

    class Point {
        int x; // 起始x坐标
        int y; // 起始y坐标
        int count; // 区域内蘑菇总数
        int endX; // 结束x坐标
        int endY; // 结束y坐标
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

零基础学并查集算法

并查集是我暑假从高手那里学到的一招,觉得真是太精妙的设计了。以前我无法解决的一类问题竟然可以用如此简单高效的方法搞定。不分享出来真是对不起party了。(pa...

56380
来自专栏计算机视觉与深度学习基础

HDU4027

本以为对线段树还是比较熟悉的,但是这题改变了我的想法。 顺着wk的题解做了这题。 拿到手就知道线段树,写完T,这时候我想起来蓝桥杯的线段树也是这样的吧,只不过那...

21070
来自专栏章鱼的慢慢技术路

炸弹人游戏

20950
来自专栏简书专栏

Python数据科学库-小测验

答:np.arange、np.array、np.ones、np.zeros、np.full

19210
来自专栏数据结构与算法

P1095 守望者的逃离

题目描述 恶魔猎手尤迪安野心勃勃,他背叛了暗夜精灵,率领深藏在海底的娜迦族企图叛变。守望者在与尤迪安的交锋中遭遇了围杀,被困在一个荒芜的大岛上。为了杀死守望者,...

29060
来自专栏Flutter入门

WAV文件格式解析及处理

RIFF全称为资源互换文件格式(Resources Interchange File Format),是Windows下大部分多媒体文件遵循的一种文件结构。RI...

1.7K20
来自专栏生信宝典

Python学习没有捷径,但可以加速,零基础九天你也可以会编程

在小学生都学Python了,你还不知道怎么开始文中介绍了Python的应用广泛,功能强大,提供了Python的在线学习视频和资料等 (收集资料是我们的最爱)。...

212100
来自专栏YoungGy

MMD_2c_FrequentItemsets

The market-basket model 主要术语 应用 规模 Association Rules 概述 思路 核心问题 计算模型 数据形式 IO分析 内...

24550
来自专栏SeanCheney的专栏

《利用Python进行数据分析·第2版》第14章 数据分析案例14.1 来自Bitly的USA.gov数据14.2 MovieLens 1M数据集14.3 1880-2010年间全美婴儿姓名14.4

本书正文的最后一章,我们来看一些真实世界的数据集。对于每个数据集,我们会用之前介绍的方法,从原始数据中提取有意义的内容。展示的方法适用于其它数据集,也包括你的。...

42950
来自专栏数据结构与算法

BZOJ1096: [ZJOI2007]仓库建设(dp+斜率优化)

Description   L公司有N个工厂,由高到底分布在一座山上。如图所示,工厂1在山顶,工厂N在山脚。由于这座山处于高原内 陆地区(干燥少雨),L公司一...

37450

扫码关注云+社区

领取腾讯云代金券