java笔试面试题（17）
在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.util.ArrayL
import java.util.S
public class LensScanner {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while (scan.hasNext()) {
int m = scan.nextInt();
int n = scan.nextInt();
int k = scan.nextInt();
int[][] mushroom = new int[k][2];
for (int i = 0; i & ++i) {
mushroom[i][0] = scan.nextInt();
mushroom[i][1] = scan.nextInt();
System.out.println(solve(m, n, k, mushroom));
scan.close();
public static int solve(int m, int n, int k, int[][] mushroom) {
int[][] graph = new int[m + 2][n + 2];
for (int i = 0; i & ++i) {
graph[mushroom[i][0]][mushroom[i][1]]++;
int max1 = 0;
int max2 = 0;
ArrayList&Integer& coordinate = new ArrayList&Integer&();
for (int i = 1; i &= ++i) {
for (int j = 1; j &= ++j) {
int temp = 0;
for (int dx = -1; dx & 2; ++dx) {
for (int dy = -1; dy & 2; ++dy) {
if (graph[i + dx][j + dy] & 0)
if (temp & max1) {
coordinate.clear();
coordinate.add(i);
coordinate.add(j);
} else if (temp == max1) {
coordinate.add(i);
coordinate.add(j);
for (int idx = coordinate.size() - 1; idx &= 0;) {
int y1 = coordinate.get(idx--);
int x1 = coordinate.get(idx--);
int[][] mask = new int[m + 2][n + 2];
for (int dx = -1; dx & 2; ++dx) {
for (int dy = -1; dy & 2; ++dy) {
mask[x1 + dx][y1 + dy]--;
for (int i = 1; i &= ++i) {
for (int j = 1; j &= ++j) {
int temp = 0;
for (int dx = -1; dx & 2; ++dx) {
for (int dy = -1; dy & 2; ++dy) {
if (graph[i + dx][j + dy] + mask[i + dx][j + dy] & 0)
if (temp & max2)
if (18 == max1 + max2)
return 18;
return (max1 + max2);
本题的所提的问题本身并不复杂，而且需求很清晰，但是由于条件限制，实现起来并不太容易。首先就是m或n可能小于3，这样每个格子都没有完整的8邻域，而且即使m和n都大于3，草坪最外围一圈格子也会没有完整的8邻域，所以这里我们可以给整个草坪（下图深色底纹的格子）的外围再加上一圈padding格子（下图中的浅色虚线格子），这样就能保证原草坪中的每个格子都有8邻域，方便我们用统一的公式计算。可以画个示意图如下：
由于题目所给蘑菇的坐标正好也是从1开始的，所以padding格子中不会有蘑菇。
题目要求两次扫描最多可以清除掉的蘑菇总数，而且每次扫描只能清除掉一个格子中的一个蘑菇，所以每次扫描最多可以清除9个蘑菇，每个格子最多可以被清除掉2个蘑菇。上述代码使用的是贪婪算法，每次都尽可能多地清除蘑菇，由于第一次符合条件的扫描位置可能不止一个（比如上图中的4个红色位置都能在一次扫描中清除掉最多5个蘑菇，但是其中只有2个位置能使第二次扫描清除掉最多4个蘑菇），所以还要针对所有第一次扫描的候选位置，结合第二次扫描的结果来得到两次扫描的最大清除量。本解法的时间复杂度为O(m·n)+k·O(m·n)=(1+k)·O(m·n)，其中k为第一个透镜扫描的所有候选位置，即代码中max1对应的所有坐标位置，所以k是不是常量级呢？
本题的解法虽然通过了牛客网的OJ，但是用贪婪算法分别求两次扫描的最大清除量之和就一定是总的全局最大清除量吗？
牛客网有同学提到，分两步单独搜索所得到的结果只是局部最优解，并举出了如下的例子说明，当m=3，n=8时，假如蘑菇分布如下：
在第一个透镜扫描时，最大的可清除数是6个，共有4种位置，如果选择清除掉中间的6个蘑菇，那么第二次最多清除掉3个蘑菇，这样就不能全清所有蘑菇了。而我上面提供的代码，把这4种情况都对第二次扫描做了联合求解，结果是能够清除掉所有蘑菇的，所以在本题使用贪婪算法并不一定不能得到全局最优解。但是我无法证明这一点，希望有同学能提供证明方法。另外，为了避免局部最优解，可以使用下述代码的暴力搜索方式，处理的大致思路和之前的代码是类似的，也需要构造padding格子，只是每次用第一个透镜扫描时都要结合第二个透镜扫描的结果，这样得到的必定是全局最优解，但是算法复杂度达到了O((m·n)^2)。如果有同学有更优雅的解法，欢迎交流学习！
public static int brutalSolve(int m, int n, int k, int[][] mushroom) {
int[][] graph = new int[m + 2][n + 2];
for (int i = 0; i & ++i) {
graph[mushroom[i][0]][mushroom[i][1]]++;
int max = 0;
for (int i = 1; i &= ++i) {
for (int j = 1; j &= ++j) {
int[][] mask = new int[m + 2][n + 2];
int max1 = 0;
for (int dx1 = -1; dx1 & 2; ++dx1) {
for (int dy1 = -1; dy1 & 2; ++dy1) {
if (graph[i + dx1][j + dy1] & 0) {
mask[i + dx1][j + dy1]--;
for (int r = 1; r &= ++r) {
for (int t = 1; t &= ++t) {
int max2 = 0;
for (int dx2 = -1; dx2 & 2; ++dx2) {
for (int dy2 = -1; dy2 & 2; ++dy2) {
if (graph[r + dx2][t + dy2] + mask[r + dx2][t + dy2] & 0)
if (max1 + max2 & max)
max = max1 + max2;
if (18 == max)
return 18;
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：43577次
积分：1290
积分：1290
排名：千里之外
原创：74篇
评论：29条
(11)(4)(30)(21)(6)(1)(1)(1)(2)(1)
(window.slotbydup = window.slotbydup || []).push({
id: '4740881',
container: s,
size: '200,200',
display: 'inlay-fix'}