网易在线笔试题 采蘑菇

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

这里采用暴力法每次都算出能检测到的最大的蘑菇数，但是一个有点儿难度的问题就是如何记录蘑菇数最多的那个透镜的位置，一遍在第二次扫描之前将那个位置的蘑菇数减一。

代码已经accept，如果要想通过在线验证，必须把类名和生成对象那两行改为Main就好了，欢迎大家交流。

import java.util.Scanner;

public class Mushroom {

    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        while(scanner.hasNext()){
            int N=scanner.nextInt();
            int M=scanner.nextInt();
            int K=scanner.nextInt();
            int[][] pos=new int[K][2];
            for(int i=0;i<K;i++){
                pos[i][0]=scanner.nextInt();
                pos[i][1]=scanner.nextInt();
            }
            Mushroom mushroom=new Mushroom();
            int[][] NM=mushroom.getNM(N, M, K, pos);
            int count = mushroom.scanMushroom(NM);
            count += mushroom.scanMushroom(NM);
            
            System.out.println(count);
        }
        
    }
    
    public int[][] getNM(int N, int M, int K, int[][] pos){
        if(N<3) N=3;
        if(M<3) M=3;
        int[][] NM=new int[N+1][M+1];
        for(int i=1;i<=N;i++){
            for(int j=1;j<=M;j++){
                NM[i][j]=0;
            }
        }
        
        for(int i=0;i<K;i++){
            ++NM[pos[i][0]][pos[i][1]];
        }
        
        return NM;
    }
    
    public int scanMushroom(int[][] NM){
        int maxCount=0; 
        // 数组是按行向量存储的
        int N=NM.length-1;
        int M=NM[0].length-1;
        
        CountAndPos rc1=getMushroomInRect(NM, 2, 2);   //记录3*3矩形内最大蘑菇数和此时矩形的中心坐标
        for(int i=2;i<=N-1;i++){
            for(int j=2;j<=M-1;j++){
                CountAndPos rc2= getMushroomInRect(NM, i, j);
                if(maxCount<rc2.countInRect){
                    rc1=rc2;
                    maxCount = rc2.countInRect;
                }
            }
        }
        
        // 扫描蘑菇后清除蘑菇
        int centerX=rc1.x;
        int centerY=rc1.y;
        for(int i=-1;i<=1;i++){
            for(int j=-1;j<=1;j++){
                if(NM[centerX+i][centerY+j]>0){
                    --NM[centerX+i][centerY+j];
                }
            }
        }    
        
        return maxCount;
    }
    
    public CountAndPos getMushroomInRect(int[][]NM,int centerX, int centerY){
        int countInRect=0;
        for(int i=-1;i<=1;i++){
            for(int j=-1;j<=1;j++){
                if(NM[centerX+i][centerY+j]>0){
                    countInRect++;
                }
            }
        }
        CountAndPos cp = new CountAndPos(countInRect,centerX,centerY);
        return cp;
    }
    
    private class CountAndPos{
        public int countInRect;
        public int x;
        public int y;
        public CountAndPos(int count, int x, int y){
            this.countInRect=count;
            this.x=x;
            this.y=y;
        }
    }

}