[编程题]扫描透镜
在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)处提莫种了一个蘑菇. 一个方格可以种无穷个蘑菇.
输出描述:
输出一行,在这一行输出一个整数,代表兰博最多可以清理多少个蘑菇.
答案转自：http://blog.csdn.net/xuelabizp/article/details/50811010
2.思路解析
首先吐槽一下，这道题有一股浓浓的翻译腔，逻辑混乱，看起来很费劲，这道题本身不难，难的是读懂题意。
解析一下这道题的已知的条件：
- 草地大小为N*M——二维数组为
N*M - 一个方格可以有多个蘑菇——数组元素的值在[0,K]区间内
- 透镜检查范围为3*3——每次检查3*3的方格有多少蘑菇
- 两个透镜——扫描两次，且有先后问题（下面详解）
故这道题的解答方法如下：
(1)读入数据N，M，K
(2)初始化土地
(3)使用第一块透镜扫描土地第一个3*3方格，并且将该方格的所有蘑菇数减1（空的不减），同时记录采集的蘑菇数mushroom1
(4)在第(3)步的基础上，使用第二块透镜扫描土地的所有个3*3方格，每扫描完一个3*3方格，记录当前方格的蘑菇数mushroom2，注意不用再减1，计算当前mushroom1+mushroom2
(5)重复(3)(4)，直到使用第一块透镜扫描完所有的土地
(6)输出mushroom1+mushroom2的最大值
注意：第一块透镜和第二块透镜扫描的3*3方格之间没有任何关系，且透镜只能知道该方格有没有蘑菇，而不知道有几块蘑菇
#include <iostream> #include <vector> using namespace std; int main() { //input data int n, m, k; while (cin>>n>>m>>k){ if (n < 3) n = 3; if (m < 3) m = 3; //initialize ground vector<vector<int> > ground(n, vector<int>(m, 0)); for (int i=0; i<k; i++){ int x, y; cin>>x>>y; ground[--x][--y]++; } int mushroomNum(0), mushroom1, mushroom2; //first scan for (int i=0; i<n-2; i++) for (int j=0; j<m-2; j++){ mushroom1 = 0; vector<vector<int> > groundNew = ground;//copy for (int row=i; row<i+3; row++) for (int col=j; col<j+3; col++) if (groundNew[row][col] > 0){ groundNew[row][col]--; mushroom1++; } //second scan for (int i=0; i<n-2; i++) for (int j=0; j<m-2; j++){ mushroom2 = 0; for (int row=i; row<i+3; row++) for (int col=j; col<j+3; col++) if (groundNew[row][col] > 0) mushroom2++; if (mushroomNum < mushroom1 + mushroom2) mushroomNum = mushroom1 + mushroom2; } } cout<<mushroomNum<<endl; } return 0; }
- second scan嵌套在first scan中
- 拓展一下，如果需要知道怎么采集蘑菇才能获得最大值，只需要在更新
mushroom时，记录第一个循环和第二个循环的i, j值，不过这里就不要都用i和j了，否则记录不了第一块透镜需要扫描的3*3方格的位置。