算法-每天一道题（24）-扫描透镜-矩阵

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

注意：每个方格被扫描一次只能清除掉一个蘑菇。

输入描述:

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

输出描述:

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

C++

#include <iostream>
#include <vector>
using namespace std;

class Solution
{
public:
    void getResult()
    {
        int N, M, K;
        while (cin >> N >> M >> K)
        {
            vector<vector<int> > v(N + 1, vector<int>(M + 1, 0));
            this->getVector(v, K);
            int final_count = 0;
            // 找两遍最大值
            for (int i = 0; i <= 1; i++)
                final_count = final_count + this->getFinalCount(N, M, v);
            cout << final_count << endl;
            v.clear();
        }
    }

    void getVector(vector<vector<int> > &v, const int K)
    {
        int x, y;
        for (int i = 0; i<K; i++)
        {
            cin >> x >> y;
            v[x][y]++;
        }
    }

    int getFinalCount(int N, int M, vector<vector<int> > &v)
    {
        int count_max = -1;
        int temp;
        int temp_x, temp_y;
        // for循环获取所在方格周围3*3方格的蘑菇数的最大值
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
            {
                temp = this->getCount(i, j, N, M, v);
                if (temp > count_max)
                {
                    count_max = temp;
                    temp_x = i;
                    temp_y = j;
                }
            }
        // 找到最大值的坐标，并把此3*3方格的蘑菇数-1
        return modifyVector(temp_x, temp_y, N, M, v);
    }

    // 求解出所在方格周围的3*3方格的蘑菇数，并把此3*3方格的蘑菇数-1
    int modifyVector(int x, int y, int N, int M, vector<vector<int> > &v)
    {
        int count = 0;
        if (v[x][y] > 0)
        {
            v[x][y]--;
            count++;
        }

        if (x > 0 && v[x - 1][y] > 0)
        {
            v[x - 1][y]--;
            count++;
        }

        if (x < N && v[x + 1][y] > 0)
        {
            v[x + 1][y]--;
            count++;
        }

        if (y > 0 && v[x][y - 1] > 0)
        {
            v[x][y - 1]--;
            count++;
        }

        if (y < M && v[x][y + 1] > 0)
        {
            v[x][y + 1]--;
            count++;
        }

        if (x > 0 && y > 0 && v[x - 1][y - 1] > 0)
        {
            v[x - 1][y - 1]--;
            count++;
        }

        if (x > 0 && y < M && v[x - 1][y + 1] > 0)
        {
            v[x - 1][y + 1]--;
            count++;
        }

        if (x < N && y > 0 && v[x + 1][y - 1] > 0)
        {
            v[x + 1][y - 1]--;
            count++;
        }

        if (x < N && y < M && v[x + 1][y + 1] > 0)
        {
            v[x + 1][y + 1]--;
            count++;
        }

        return count;
    }

    // 求解出所在方格周围的3*3方格的蘑菇数
    int getCount(int x, int y, int N, int M, const vector<vector<int> > v)
    {
        int count = 0;
        if (v[x][y] > 0)
            count++;

        if (x > 0 && v[x - 1][y] > 0)
            count++;

        if (x < N && v[x + 1][y] > 0)
            count++;

        if (y > 0 && v[x][y - 1] > 0)
            count++;

        if (y < M && v[x][y + 1] > 0)
            count++;

        if (x > 0 && y > 0 && v[x - 1][y - 1] > 0)
            count++;

        if (x > 0 && y < M && v[x - 1][y + 1] > 0)
            count++;

        if (x < N && y > 0 && v[x + 1][y - 1] > 0)
            count++;

        if (x < N && y < M && v[x + 1][y + 1] > 0)
            count++;

        return count;
    }
};

int main()
{
    Solution *s = new Solution();
    s->getResult();
    return 0;
}

/*
解题思路：

遍历矩阵，求出方格所在的周围3*3方格的蘑菇数的最大值，
找到最大值坐标之后，把周围3*3方格的蘑菇数-1，记录下扫描的蘑菇数。
再进行第二遍，累加扫描的蘑菇数。
*/