首页 > 试题广场 >

扫描透镜

[编程题]扫描透镜

热度指数：15129 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

在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)处提莫种了一个蘑菇.
一个方格可以种无穷个蘑菇.

输出描述:

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

算法知识视频讲解

暴力

先把蘑菇最多的九宫格清掉，再把蘑菇最多（相对于原始，蘑菇次多）的九宫格清掉

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while((line = br.readLine()) != null){
            String[] params = line.split(" ");
            int n = Integer.parseInt(params[0]), m = Integer.parseInt(params[1]), k = Integer.parseInt(params[2]);
            int[][] grid = new int[n][m];
            for(int i = 0; i < k; i++){
                String[] pair = br.readLine().split(" ");
                int x = Integer.parseInt(pair[0]) - 1, y = Integer.parseInt(pair[1]) - 1;
                grid[x][y] = 1;
            }
            int max = 0, x = 0, y = 0;
            for(int i = 0; i < n - 2; i++){
                for(int j = 0; j < m - 2; j++){
                    int temp = sum(grid, i, j);
                    if(temp > max){
                        max = temp;
                        x = i;
                        y = j;
                    }
                }
            }
            int res = max;
            for(int i = 0; i < 3; i++){
                for(int j = 0; j < 3; j++){
                    grid[x + i][y + j] = 0;
                }
            }
            max = 0;
            x = 0;
            y = 0;
            for(int i = 0; i < n - 2; i++){
                for(int j = 0; j < m - 2; j++){
                    int temp = sum(grid, i, j);
                    if(temp > max){
                        max = temp;
                        x = i;
                        y = j;
                    }
                }
            }
            res += max;
            System.out.println(res);
        }
    }
    
    private static int sum(int[][] grid, int x, int y) {
        int res = 0;
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                res += grid[x + i][y + j];
            }
        }
        return res;
    }
}

发表于 2022-02-23 22:19:42 回复(0)

Java

qianhuan

import java.util.Scanner;
public class Main {
    /**
     * 得到起点为x,y的扫描的蘑菇数量
     */
    public static int getArea(int[][] map,int x,int y){
        int sum = 0;
        for (int i = x; i < x+3 && i < map.length; i++) {
            for (int j = y; j < y+3 && j < map[i].length; j++) {
                if(map[i][j] > 0) sum++;
            }
        }
        return sum;
    }
    /**
     * 得到可以清除的最多蘑菇数量
     */
    public static int getMaxClear(int[][] map){
        int max = 0;
        int x = 0;
        int y = 0;
        //得到可以清除的区域
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                int area = getArea(map, i, j);
                if(area > max){
                    max = area;
                    x = i;
                    y = j;
                }
            }
        }

        //清除蘑菇
        for (int i = x; i < x+3 && i < map.length; i++) {
            for (int j = y; j < y+3 && j < map[i].length; j++) {
                if(map[i][j] > 0) map[i][j]--;
            }
        }
        return max;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int k = sc.nextInt();
            int x = 0;
            int y = 0;
            int[][] map = new int[n][m];
            for (int i = 0; i < k; i++) {
                x = sc.nextInt()-1;
                y = sc.nextInt()-1;
                map[x][y]++;
            }

            int sum = 0;
            //求出第一次清除最多的蘑菇
            sum += getMaxClear(map);
            //求出第二次清除最多的蘑菇
            sum += getMaxClear(map);
            System.out.println(sum);
        }
    }
}

发表于 2017-10-12 16:24:27 回复(0)

Java

熊小乐9book

   importjava.util.Scanner;  
   publicclassMain {  

        publicstaticvoidmain(String[] args) {  
           Scanner in
    =newScanner(System.in);  
           intn, m, k;  
           int[][] lawn;  

            while(in.hasNextInt()) {  
               n = in.nextInt();  
               m = in.nextInt();  
               k =
    in.nextInt();  
               lawn
    =newint[n][m];//n=1 or m=1 is possible!!!  
               for(inti =0; i
    < k; i++) {  

                    lawn[in.nextInt() -1][in.nextInt() -1]++;  
               }  

                System.out.println(scan(lawn) + scan(lawn));  
           }  
           in.close();  
       }  
       staticintscan(int[][]
    lawn) {  
           intx =0, y =0, max
    =0;  
           intn = lawn.length
    >3? lawn.length -2:1;  
           intm =
    lawn[0].length >3? lawn[0].length -2:1;  
           for(inti =0; i <
    n; i++) {  
               for(intj =0; j
    < m; j++) {  
                   intcount =
    countBoom(lawn, i, j);  
                   if(count
    > max) {  
                       max =
    count;  
                       x = i;  
                       y = j;  
                   }  
               }  
           }  
           if(max >0) {  
               clearBoom(lawn,
    x, y);  
           }  
           returnmax;  
       }  

        staticintcountBoom(int[][] lawn,intx,inty) {  
           intcount =0;  
           intn = lawn.length
    < x +3? lawn.length : x +3;  
           intm =
    lawn[0].length < y +3? lawn[0].length : y +3;  
           for(inti = x; i
    < n; i++) {  
               for(intj = y; j
    < m; j++) {  

                    if(lawn[i][j] >0) {  

                        count++;  
                   }  
               }  
           }  
           returncount;  
       }  

        staticvoidclearBoom(int[][] lawn,intx,inty) {  
           intn = lawn.length
    < x +3? lawn.length : x +3;  
           intm =
    lawn[0].length < y +3? lawn[0].length : y +3;  
           for(inti = x; i
    < n; i++) {  
               for(intj = y; j
    < m; j++) {  

                    if(lawn[i][j] >0) {  

                        lawn[i][j]--;  
                   }  
               }  
           }  
       }  
   }  

发表于 2017-06-13 18:16:21 回复(0)

Java

詆調壹點

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			if(n < 3) n = 3;
			if(m < 3) m = 3;
			int[][] arr = new int[n][m];
			int k = sc.nextInt();
			for (int i = 0; i < k; i ++ ) {
				int x = sc.nextInt() - 1;
				int y = sc.nextInt() - 1;
				arr[x][y] ++ ;
			}
			int[] first = scan(arr);
			clean(arr, first[1], first[2]);
			int[] second = scan(arr);
			System.out.println(first[0] + second[0]);
		}
	}
	public static void clean(int[][] arr, int x, int y) {
		for (int i = x - 1; i <= x + 1; i ++ )
			for (int j = y - 1; j <= y + 1; j ++ )
				if(arr[i][j] > 0) arr[i][j] -- ;
	}
	public static int[] scan(int[][] arr) {
		int x = 0;
		int y = 0;
		int max = 0;
		// 以i,j为中心点.扫描四周3*3方格
		for (int i = 1; i < arr.length - 1; i ++ ) {
			for (int j = 1; j < arr[0].length - 1; j ++ ) {
				int sum = 0;
				for (int u = i - 1; u <= i + 1; u ++ ) {
					for (int v = j - 1; v <= j + 1; v ++ ) {
						if(arr[u][v] > 0) sum ++ ;
					}
				}
				if(sum > max) {
					max = sum;
					x = i;
					y = j;
				}
			}
		}
		int[] res = {max, x, y};
		return res;
	}
}

发表于 2016-09-08 01:14:11 回复(0)

Java

苏果飞

///本来觉得暴力搜索会超时，但看大家都这么做，我也自己写了一个暴力搜索的。

读题意，知道，第一次扫面找到可以清除的最大数，清除后再次扫描得到最大数，两次最大数相加即为所求的结果数。即，最优解不会出现，第一次并不清除最大值，而第二次清除最大值的情况，也就是可以使用暴力搜索的前提条件。再有就是，第一次的最大值有多个的情况下（这里说的多个情况，说的是下标不同的情况。），需要遍历清除所有的情况，否则，结果不为最优。

主要调用了三个函数。

其中，scan函数用来扫描九宫格中有蘑菇的最大个数，并将所有的最大值的情况用一个arraylist将下标存起来，方便第一次扫描清除相应九宫格中的蘑菇，为第二次扫描做准备。

clear函数通过数组和下标对对应的九宫格进行一次清除，当然清除前要先判断对应下标是否有值。

Main函数主要实现整个逻辑。先调用scan函数 得到第一次的最大值和对应最大值的下标（注意，这里可能有多组。）使用for循环，遍历所有的最大值情况，找到第二次的最大值。相加，得到最终的结果。

//////还有需要注意的是，所给数组的下标是从1开始！

import java.util.Scanner;
import java.util.ArrayList;

public class Main{
	public static int scan(int[][] arr, int n, int m, ArrayList<Integer> arrList) {
		int max = 0;
		for(int i = 0; i < n-2; i++){
			for(int j = 0; j < m-2; j++){
				int temp = 0;
				for(int p = i; p < i + 3; p++){
					for(int q = j; q < j + 3; q++){
						if(arr[p][q] > 0){
							temp++;
						}
					}
				}
				if(temp > max){
					max = temp;
					arrList.clear();
					arrList.add(i);
					arrList.add(j);
				}else if(temp == max){
					arrList.add(i);
					arrList.add(j);
				}
			}
		}
		return max;
	}

	public static int[][] clear(int[][] arr, int x, int y){
		for(int i = x; i < x + 3; i++){
			for(int j = y; j < y + 3; j++){
				if(arr[i][j] > 0){
					arr[i][j]--;
				}
			}
		}
		return arr;
	}
	
	public static void Main(int[][] arr, int n, int m){
		ArrayList<Integer> arrList = new ArrayList<Integer>();
		int max = 0;
		int max1 = 0;
		max = scan(arr,n,m,arrList);
		for(int i = 0; i < arrList.size()-1; i+=2){
			int[][] newArr = new int[n][m];
			ArrayList<Integer> newArrayList = new ArrayList<Integer>();
			int temp = 0;
			int x = arrList.get(i);
			int y = arrList.get(i+1);
			newArr = clear(arr,x,y);
			temp = scan(newArr,n,m,newArrayList);
			if(temp > max1){
				max1 = temp;
			}
		}
		
		System.out.println(max+max1);
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			int k = sc.nextInt();
			if(n < 3){
				n = 3;
			}
			if(m < 3){
				m = 3;
			}
			int[][] arr = new int[n+1][m+1];
			for (int i = 0; i < k; i++) {
				int x = sc.nextInt();
				int y = sc.nextInt();
				arr[x][y] += 1;
			}
			
			Main(arr,n+1,m+1);
		}
		sc.close();
	}
}

发表于 2016-08-16 10:29:53 回复(0)

Java

隔三岔五的小幸福

PS：3*3的网格，没想明白，边缘的不能扫描到吗，不应该是4*4吗
我的笨方法：
//将每个格子蘑菇的数量放入2维数组R1中，设置新的2维数组R2，
//R1[i][j]>0时，R2[i][j]=1(每次只能打掉一个蘑菇)
//统计R2中每3*3网格中的数量和，最大地方扫描
//返回数组result[3]，result[0]=最大的打掉数,result[1]=i,result[2]=j
//根据第一次扫描后得到的i，j值更新数组，sum[i][j]--
//第二次扫描  import java.util.Scanner;
public class Main {

	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[] mogux = new int[K];
			int[] moguy = new int[K];
			for(int i=0; i<K; i++){
				mogux[i] = scanner.nextInt();
				moguy[i] = scanner.nextInt();
			}
//			int sum = 0;
			int[][] sum = new int[N+1][M+1];
			for(int i=0; i<K; i++){
				if(mogux[i]>N || mogux[i]<0 || moguy[i]>M || moguy[i]<0){
					System.out.println("蘑菇数据错误");
				}else{
					sum[mogux[i]][moguy[i]]++;
				}
			}
			int[] result1 = getMaxSum(sum);
			//更新2维数组
			for(int i=result1[1]-1; i<=result1[1]+1; i++){
				for(int j=result1[2]-1; j<=result1[2]+1; j++){
					sum[i][j]--;
				}
			}
			int[] result2 = getMaxSum(sum);
			System.out.println(result1[0]+result2[0]);
			
		}
	}
	
	
	public static int[] getMaxSum(int[][] sum){
		int[] result = new int[3];
		int[][] sumceshi = new int[sum.length][sum[0].length];
		for(int i=0; i<sum.length; i++){
			for(int j=0; j<sum[0].length; j++){
				if(sum[i][j]>0){
					sumceshi[i][j] = 1;
				}
			}
		}
		for(int i=2; i<sum.length-1; i++){
			for(int j=2; j<sum[0].length-1; j++){
				int sum0 = 0;
				sum0 = sumceshi[i-1][j-1] + sumceshi[i-1][j] + sumceshi[i-1][j+1] 
						+ sumceshi[i][j-1] + sumceshi[i][j] + sumceshi[i][j+1] 
						+sumceshi[i+1][j-1] + sumceshi[i+1][j] + sumceshi[i+1][j+1];
				if(sum0>result[0]){
					result[0] = sum0;
					result[1] = i;
					result[2] = j;
				}
			}
		}
		
		return result;
	}

}

编辑于 2016-08-02 17:27:48 回复(0)

Java

克逊

/* 这里要注意输入的k个数的起始位置是从1开始的，所以需要转换成0开始，不然会溢出 */
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		
		Scanner in = new Scanner(System.in);
		
		while (in.hasNextInt()) {
			int n = in.nextInt();
			int m = in.nextInt();
			int k = in.nextInt();
			if (n<3) n=3;
			if (m<3) m=3;
			
			int[][] array = new int[n][m];
			for (int i=0; i<k; i++) {
				int x = in.nextInt();
				int y = in.nextInt();
					array[x-1][y-1]++;
			}
			
			int m1 = findMax(array);
			int m2 = findMax(array);
			System.out.println(m1+m2);
		}
		
	}
	
	public static int findMax(int[][] array) {
		
		int lx = array.length;
		int ly = array[0].length;
		int max = 0;
		int startx = 0;
		int starty = 0;
		
		for (int i=0; i<=lx-3; i++) {
			
			for (int j=0; j<=ly-3; j++) {
				
				int tempMax = 0;
				for (int m=i; m<i+3; m++) {
					for (int n=j; n<j+3; n++) {
						if (array[m][n] > 0) {
							tempMax++;
						}
					}
				}
				
				if (tempMax > max) {
					max = tempMax;
					startx = i;
					starty = j;
				}
			}
		}
		
		for (int i=startx; i<startx+3; i++) {
			for (int j=starty; j<starty+3; j++) {
				array[i][j]--;
			}
		}
		
		return max;
	}
	

}

发表于 2016-08-01 21:47:21 回复(0)