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

网易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坐标
    }
}