网易5：扫描透镜

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

#include<iostream>
#include<vector>
using namespace std;
/*
基本思路，先找出第一次最大的，然后清除，再找出最大的，两次之和即为最多清除的。
但是有个陷阱或者说是我们读题目不仔细，就是每个空格可能会有多个蘑菇，而我们每次只能
清除一个蘑菇，所以每次遍历时的最大的应该是多少个方格里面有蘑菇（即数量大于0），这样
找出来的才是清除最大的，找出来之后当然是要将这些方格里面有蘑菇的都减1.然后再找一次最大的
*/
//循环遍历每个方格，并记录当前方格3*3范围内最多的蘑菇数量和对应的中心地址
int count_grid(vector<vector<int> > &field,int n,int m)
{
    int maxMarshroom=0,marshroom=0,maxX=0,maxY=0;
    int x0=0,x1=n-1,y0=0,y1=m-1;
    //外层坐标x从1到n-1,y从1到m-1，这样便于遍历3*3范围
    for(int i=1;i<n-1;i++)
    {
        for(int j=1;j<m-1;j++)
        {
            //遍历坐标从i-1到i+1
            for(int x=i-1;x<=i+1;x++)
            {
                for(int y=j-1;y<=j+1;y++)
                {
                    if(field[x][y]>0)
                        marshroom++;
                }
            }
            //若找到更大的蘑菇群，则更换当前坐标
            if(maxMarshroom<marshroom)
            {
                maxMarshroom=marshroom;
                maxX=i;
                maxY=j;
            }
            marshroom=0;
        }
    }
    //找到最大的蘑菇群后，减去被扫过的区域，一个坐标减去一个，以便第二次使用
    for(int i=maxX-1;i<=maxX+1;i++)
    {
        for(int j=maxY-1;j<=maxY+1;j++)
        {
            field[i][j]--;
        }
    }
    return maxMarshroom;
}
int main()
{
    int n,m,k;
    //根据输入数组初始化矩阵，有蘑菇处显示蘑菇数量，没蘑菇处为0
    while(cin>>n>>m>>k){
        //定义N*M的矩阵:注意这个需要先输入n,m后才能定义，不然会提示n,m未初始化错误
        vector<vector<int> > field(n,vector<int>(m,0));
        int x,y;
        for(int i=0;i<k;i++)
        {
            cin>>x>>y;
            field[x-1][y-1]+=1;
        }
        //循环遍历每个方格，记录每个方格3*3区域内蘑菇数量
        int maxMarshroom_1=count_grid(field,n,m);
        int maxMarshroom_2=count_grid(field,n,m);
        cout<<maxMarshroom_1+maxMarshroom_2<<endl;
    }
    return 0;
}