掃描透鏡 在N*M的草地上,小明種了K個蘑菇,蘑菇爆炸的威力極大,小華不想貿(mào)然去闖,而且蘑菇是隱形的.只 有一種叫做掃描透鏡的物品可以掃描出隱形的蘑菇,于是他回了一趟戰(zhàn)爭學(xué)院,買了2個掃描透鏡,一個 掃描透鏡可以掃描出(3*3)方格中所有的蘑菇,然后小華就可以清理掉一些隱形的蘑菇. 問:小華最多可以清理多少個蘑菇?

輸入描述:

第一行三個整數(shù):N,M,K,(1≤N,M≤20,K≤100),N,M代表了草地的大小; 接下來K行,每行兩個整數(shù)x,y(1≤x≤N,1≤y≤M).代表(x,y)處提莫種了一個蘑菇. 一個方格可以種無窮個蘑菇.

輸出描述:

輸出一行,在這一行輸出一個整數(shù),代表蘭博最多可以清理多少個蘑菇.

解題
掃描鏡子，掃描了，都清理掉，答案不就是K嗎？

無法理解題意

討論中下面講解 一個掃描透鏡可以掃描出（3*3）方格中的所有蘑菇，問最多可清理多少個蘑菇就是求二維數(shù)組中哪一塊（3*3）區(qū)域中的蘑菇數(shù)最多。 有兩個透鏡，那么最多可清理的蘑菇數(shù)就是第一個透鏡最多清理的加上第二個透鏡最多清理的（將求最多清理蘑菇數(shù)寫成函數(shù)）。
需要注意的是對于每個方格如果其中有多個蘑菇那么一次掃描只能清理掉一個蘑菇。
這要求我們在求出第一個最優(yōu)解后要對二維數(shù)組中的相應(yīng)方格中的蘑菇數(shù)進行減1操作 1.暴力找到第一個3*3小方格內(nèi)非空的個數(shù)
2.該方格內(nèi)數(shù)減1
3.暴力找第二個
這樣的方格就是，非空元素最大

import java.util.Scanner; public class Main{public static void main(String[] args){Scanner in = new Scanner(System.in);while(in.hasNext()){int n = in.nextInt();int m = in.nextInt();int k = in.nextInt();if(n<3)n=3;if(m<3)m=3;int[][] A = new int[n][m];for(int i =0;i<k;i++){int x = in.nextInt();int y = in.nextInt();A[x-1][y-1]++;}int first[] = new int[3];int second[] = new int[3];Scan(A,first);for(int i = first[1];i< first[1] + 3;i++){for(int j = first[2];j<first[2] + 3;j++){if(A[i][j]>0)A[i][j]--;}}Scan(A,second);System.out.println(first[0] + second[0]);}}public static void Scan(int[][] A,int[] arr){int n = A.length;int m = A[0].length;for(int i =0;i<n - 2;i++){for(int j =0;j< m -2;j++){int num = 0;for(int u = i;u<i+3;u++){for(int v =j;v<j+3;v++){if(A[u][v] >0){num++;}}}if(arr[0]<= num){arr[0] = num;arr[1] = i;arr[2] = j;}}}} }

?

轉(zhuǎn)載于:https://www.cnblogs.com/theskulls/p/5280741.html

總結(jié)

以上是生活随笔為你收集整理的网易2016研发工程师编程题：扫描透镜的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。