在N*M的草地上,提莫种了K个蘑菇,蘑菇爆炸的威力极大,兰博不想贸然去闯,而且蘑菇是隐形的.只
有一种叫做扫描透镜的物品可以扫描出隐形的蘑菇,于是他回了一趟战争学院,买了2个扫描透镜,一个
扫描透镜可以扫描出(3*3)方格中所有的蘑菇,然后兰博就可以清理掉一些隐形的蘑菇. 问:兰博最多可以清理多少个蘑菇?
注意：每个方格被扫描一次只能清除掉一个蘑菇。
[编程题]扫描透镜
缺少前提条件：一次只能清除一个方格里头的一个蘑菇，而不是所有！！！！（浪费了我半个多小时来检查问题）
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Main {
public static int LENGTH = 2;
public static void main(String[] args) throws FileNotFoundException {
int N = 0, M = 0, K;
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
// 1.输入数据
N = scanner.nextInt();
M = scanner.nextInt();
K = scanner.nextInt();
int[][] num = new int[N][M];// 蘑菇分布
while (K > 0) {
int x = scanner.nextInt() - 1;
int y = scanner.nextInt() - 1;
if (x < N && y < M) {
num[x][y]++;
K--;
}
}
// 2.统计个数
Point firstPoint = findMaxNum(N, M, num);
clear(firstPoint, num, N, M);
Point secondPoint = findMaxNum(N, M, num);
System.out.println(firstPoint.count + secondPoint.count);
}
}
// x,y
public static Point getNumInLocation(int N, int M, int[][] num, int startX, int startY) {
int endX, endY;
// 1.确定区域
if (startX + LENGTH > N - 1) {
endX = N - 1;
} else {
endX = startX + LENGTH;
}
if (startY + LENGTH > M - 1) {
endY = M - 1;
} else {
endY = startY + LENGTH;
}
// 2.统计个数
Point point = new Main().new Point();
point.count = 0;
point.x = startX;
point.y = startY;
point.endX = endX;
point.endY = endY;
for (int i = startX; i <= endX; i++) {
for (int j = startY; j <= endY; j++) {
if (num[i][j] > 0) {
point.count++;
}
}
}
return point;
}
// 统计能扫描到的最大值
private static Point findMaxNum(int N, int M, int[][] num) {
Point point = new Main().new Point();
point.count = 0;
point.x = 0;
point.y = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
Point tempPoint = getNumInLocation(N, M, num, i, j);
if (point.count < tempPoint.count) {
point = tempPoint;
}
}
}
return point;
}
// 第一次扫描完 进行清除操作
private static void clear(Point point, int[][] num, int N, int M) {
for (int i = point.x; i <= point.endX; i++) {
for (int j = point.y; j <= point.endY; j++) {
if (num[i][j] > 0 && i < N & j < M) {
num[i][j]--;
}
}
}
}
class Point {
int x;// 起始坐标
int y;// 起始坐标
int count;// 区域内总数
int endX;// 结束坐标
int endY;// 结束坐标
}
}
发表于 2016-03-20 22:00:03
回复(13)
如上图所示，第1次扫描的最大结果是6，但是最大值位置有3个，若选择第1次清除最中间的6个蘑菇，则第2次扫描最大结果只有3。即局部最优解并不是全局最优解。第1次选择左侧的6个蘑菇，第2次选择右侧的6个蘑菇，则全局最优解为12。
针对上述描述的易错点，在第1次扫描时候除了保存最大值外，还应该保存最大值的位置。第2次扫描的最大结果要建立在第1次扫描结果位置的基础上。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int cover9(vector<vector<int>> &mush, int row, int col) {
int count = 0;
for (int i = row - 1; i<row + 2; i++) {
for (int j = col - 1; j<col + 2; j++) {
if (mush[i][j] != 0) {
count += 1;
}
}
}
return count;
}
vector<vector<int>> searchMax(vector<vector<int>> &mush, int N, int M) {
vector<vector<int>> res(N+2, vector<int>(M+2, 0));
int temp = 0;
int maxCount = -1;
for (int i = 1; i<=N; i++) {
for (int j = 1; j<=M; j++) {
temp = cover9(mush, i, j);
if (temp > maxCount) {
res.clear();
res.resize(N + 2, vector<int>(M + 2,0));
maxCount = temp;
res[i][j] = maxCount;
}
if (temp == maxCount) {
res[i][j] = maxCount;
}
}
}
return res;
}
int removeSearch(int N,int M,int row,int col,vector<vector<int>> mush) {
for (int i = row - 1; i<row + 2; i++) {
for (int j = col - 1; j<col + 2; j++) {
mush[i][j] = (mush[i][j] == 0) ? 0 : mush[i][j] - 1;
}
}
int temp = 0;
int maxCount = -1;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
temp = cover9(mush, i, j);
if (temp >= maxCount) {
maxCount = temp;
}
}
}
return maxCount;
}
int main() {
int N, M, K;
int tempX, tempY;
while (cin >> N >> M >> K) {
vector<vector<int>> mush(N+2, vector<int>(M+2, 0));
for (int i = 0; i<K; i++) {
cin >> tempX;
cin >> tempY;
mush[tempX][tempY] += 1;
}
int res1;
int res2 = -1;
vector<vector<int>> max1 = searchMax(mush, N, M);
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (max1[i][j] != 0) {
res1 = max1[i][j];
//移除该区域的蘑菇,并进行第2次搜索
res2 = max(res2,removeSearch(N,M,i, j, mush));
}
}
}
cout <<res1+res2 << endl;
}
return 0;
}
发表于 2017-03-20 10:00:12
回复(2)
通过编译。 需要注意草坪的边长 M或者N 有可能小于3
def scanMap(arr):
row = len(arr)
col = len(arr[0])
most = 0
x = 0
y = 0
if row >=3:
label = 3
rowrange = row-2
else:
label = row
rowrange = 1
if col >= 3:
label2 =3
colrange = col-2
else:
label2 = col
colrange = 1
for i in range(rowrange):
for j in range(colrange):
num = 0
for m in range(label):
for n in range(label2):
if arr[i+m][j+n] > 0:
num += 1
if num > most:
most = num
x = i
y = j
for i in range(x, x+label):
for j in range(y,y+label2):
if arr[i][j] > 0:
arr[i][j] -= 1
return most, arr
while(1):
try:
line = [int(x) for x in raw_input().split()]
N = line[0]
M = line[1]
K = line[2]
arr = [[0 for i in range(M)] for j in range(N)]
for i in range(K):
locate = [int(x) for x in raw_input().split()]
arr[locate[0]-1][locate[1]-1] += 1
get = 0
most, arr = scanMap(arr)
get += most
most, arr = scanMap(arr)
get += most
print(get)
except:
exit(0)
发表于 2016-03-17 10:47:12
回复(0)
感觉这道题缺省一个条件：就是每一个方格一次只能清理掉一个蘑菇。
参考前人思路总结如下思路：
- 获得蘑菇分布vector<vector<int>> a;
- 拷贝为b, 进行第一次清除，同时在b上减去，再进行第二次清除；
- 重复以上步骤，得到最大值。
#include<iostream>#include<vector>#include<algorithm>using namespace std;int main(){int N, M, K;while(cin >> N >> M >> K) {if(N < 3)N = 3;if(M < 3)M = 3;vector<vector<int>> grand1(N, vector<int>(M, 0));vector<vector<int>> grand2;int result = 0;int i, j;int first = 0, second = 0;while(K-- > 0) {cin >> i >> j;++grand1[i - 1][j - 1];}grand2 = grand1;for(int i = 0; i < N - 2; ++i)for(int j = 0; j < M - 2; ++j) {grand2 = grand1;first = 0;for(int m = i; m < i + 3; ++m) {for(int n = j; n < j + 3; ++n) {if(grand2[m][n] > 0) {++first;--grand2[m][n];}}}for(int o = 0; o < N - 2; ++o)for(int p = 0; p < M - 2; ++p) {second = 0;for(int e = o; e < o + 3; ++e)for(int f = p; f < p + 3; ++f) {if(grand2[e][f] > 0)++second;}result = max(result, first + second);}}cout << result << endl;}return 0;}
编辑于 2016-03-02 17:27:47
回复(2)
#include<iostream>
using namespace std;
int x,y,m,n,xx,yy;
int MAX(int aa[21][21]){
int i,j,temp = 0,temp1=0,max = 0;
for(i=1;i<=3;i++){//初始temp为地图前3行前3列的可扫蘑菇数。
for(j=1;j<=3;j++)
if(aa[i][j] > 0)
temp ++;
}
temp1 = temp;
for(i=3;i<=n;i++){
for(j=3;j<=m;j++){
if(j>3)
temp1 = temp1 - aa[i-2][j-3] - aa[i-1][j-3] - aa[i][j-3] + aa[i-2][j] + aa[i-1][j] + aa[i][j];
if(temp1 > max){
max = temp1; x = i; y = j;
}
}
temp1 = temp;
temp1 = temp1 - aa[i-2][1] - aa[i-2][2] - aa[i-2][3] + aa[i+1][1] + aa[i+1][2] + aa[i+1][3];
temp = temp1;
}
xx = x; yy = y;
return(max);
}
int main(){
int k,i,j;
while( cin >> n >> m >> k){
int aa[21][21]={0},bb[21][21]={0},x,y,temp1=0,temp = 0,max=0,nextmax=0;
for(i=0;i<k;i++){
cin >> x >> y;
aa[x][y] = 1;
bb[x][y] ++;
}
int k = MAX(aa);
for(i=xx-2;i<=xx;i++){//处理数组bb，bb为删除第一轮蘑菇后的地图
for(j=yy-2;j<=yy;j++)
if(bb[i][j] > 0)
bb[i][j]--;
}
for(i=1;i<=n;i++){
for(j=1;j<=m;j++)
if( bb[i][j]>0)
bb[i][j] = 1;
}
cout << MAX(aa) + MAX(bb) <<endl;
}
return 0;
}
发表于 2017-07-05 15:29:08
回复(0)
// 不能分成两步进行贪心
// 我直接对所有两步后的结果遍历
#include <stdio.h>
int main() {
int N, M, K, x, y, u, v;
int max;
int dx[] = { -1, -1, -1, 1, 1, 1, 0, 0, 0 }, dy[] = { -1, 0, 1, -1, 0, 1, -1, 0, 1 };
while (scanf("%d %d %d", &N, &M, &K) != EOF) {
max = 0;
int map[30][30] = {0};
int one[30][30] = {0};
int two[30][30] = {0};
for (int i = 0; i < K; i++) {
scanf("%d %d", &x, &y);
map[x][y] += 1;
}
for (x = 1; x <= N; x++) {
for (y = 1; y <= M; y++) {
int sum0 = 0;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
one[i][j] = 0;
for (int i = 0; i < 9; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
if (xx >= 1 && xx <= N && yy >= 1 && yy <= M && map[xx][yy] > one[xx][yy]) {
one[xx][yy] += 1;
sum0 += 1;
}
}
for (u = 1; u <= N; u++) {
for (v = 1; v <= M; v++) {
int sum1 = 0;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
two[i][j] = 0;
for (int i = 0; i < 9; i++) {
int uu = u + dx[i];
int vv = v + dy[i];
if (uu >= 1 && uu <= N && vv >= 1 && vv <= M && map[uu][vv] > (one[uu][vv] + two[uu][vv])) {
two[uu][vv] += 1;
sum1 += 1;
}
}
if (sum0 + sum1 > max)
max = sum0 + sum1;
}
}
}
}
printf("%d\n", max);
}
return 0;
}
发表于 2017-03-23 12:07:50
回复(1)
水题。注意每次除蘑菇只能每个格子除一个。
#include <bits/stdc++.h>
using namespace std;
int cover9(vector<vector<int> > &a,int row,int col){
int c=0;
for(int i=row-1;i<row+2;++i)
for(int j=col-1;j<col+2;c+=(a[i][j++]?1:0));
return c;
}
int search(vector<vector<int> > &area,int N,int M){
int sum=0,tmp,x,y;
for(int i=1;i<=N;++i){
for(int j=1;j<=M;++j){
tmp = cover9(area,i,j);
if (tmp > sum){
sum=tmp;
x=i,y=j;
}
}
}
for(int i=x-1;i<x+2;++i)
for(int j=y-1;j<y+2;++j)
area[i][j]=(area[i][j]?area[i][j]-1:0);
return sum;
}
int main(){
for(int N,M,K;cin>>N>>M>>K;){
vector<vector<int> > area(N+2,vector<int>(M+2,0));
for(int x,y;K-- && cin>>x>>y;++area[x][y]);
cout<<search(area,N,M)+search(area,N,M)<<endl;
}
return 0;
}
发表于 2016-08-23 19:32:17
回复(0)
基本思路，先找出第一次最大的，然后清除，再找出最大的，两次之和即为最多清除的。
但是有个陷阱或者说是我们读题目不仔细，就是每个空格可能会有多个蘑菇，而我们每次只能
清除一个蘑菇，所以每次遍历时的最大的应该是多少个方格里面有蘑菇（即数量大于0），这样
找出来的才是清除最大的，找出来之后当然是要将这些方格里面有蘑菇的都减1.然后再找一次最大的
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
int N = 0;
int M = 0;
int K = 0;
while (scanner.hasNext()) {
N = scanner.nextInt();
M = scanner.nextInt();
K = scanner.nextInt();
if (N < 1 || N > 20)
return;
if (M < 1 || M > 20)
return;
if (K < 0 || K > 100)
return;
int[][] land = new int[M + 1][N + 1];
int x = 0, y = 0;
for (int i = 0; i < K; i++) {
x = scanner.nextInt();
y = scanner.nextInt();
land[y][x]++;
}
int max = 0, secondmax = 0;
max = findMaxIn(land);
secondmax = findMaxIn(land);
System.out.println(max + secondmax);
}
}
private static int findMaxIn(int[][] land) {
int max = 0;
int maxX = 0, maxY = 0;
int num = 0;
for (int i = 1; i < land.length - 1; i++) {
for (int j = 1; j < land[0].length - 1; j++) {
for (int k = i-1; k <=i+1; k++) {
for (int m = j-1; m <=j+1; m++) {
if(land[k][m]>0)
num++;
}
}
if (num > max) {
max = num;
maxX = j;
maxY = i;
}
num = 0;
}
}
for (int i = maxY - 1; i <= maxY + 1; i++) {
for (int j = maxX - 1; j <= maxX + 1; j++) {
if (land[i][j] > 0)
land[i][j]=land[i][j]-1;
}
}
return max;
}
}
发表于 2016-05-04 20:39:56
回复(2)
答案错误:您提交的程序没有通过所有的测试用例 测试用例: 14 8 47 11 5 7 2 1 1 12 4 8 7 13 2 6 5 4 5 1 5 5 3 4 1 5 3 7 8 3 3 4 3 3 7 5 2 10 8 11 7 1 7 11 6 12 8 13 2 2 8 10 2 12 4 10 2 1 5 5 8 12 5 10 8 4 5 1 6 8 6 10 3 4 8 8 2 3 4 14 8 4 8 12 8 11 6 12 1 10 3 5 2 8 1 6 6 对应输出应该为: 9 矩阵：
000000000
010002110
000000001
000110010
010102002
002200001
000001100
001000001
011000110
000000000
002200002
000001210
010021002
002000000
000000001
最多不应该是7+7=14吗？？？
发表于 2015-11-30 08:12:36
回复(6)
#include<iostream>#include<vector>using namespace std;int main(){intn, m, k;intx, y;while(cin >> n >> m >> k){intmax = 0;inttemp1 = 0;inttemp2 = 0;if(n <= 2)n = 3;if(m <= 2)m = 3;vector<vector<int> > a(n);vector<vector<int> > b;for(inti = 0; i < n; i++)a[i].resize(m);for(inti = 0; i < n; i++)for(intj = 0; j < m; j++)a[i][j] = 0;for(inti = 0; i < k; i++){cin >> x >> y;x--;y--;a[x][y]++;}b = a;for(inti = 0; i < n - 2; i++)for(intj = 0; j < m - 2; j++){b = a;temp1 = 0;for(intp = i; p < i + 3; p++)for(intq = j; q < j + 3; q++){if(b[p][q]>0)temp1++;b[p][q]--;}for(inte = 0; e < n - 2; e++)for(intf = 0; f < m - 2; f++){temp2 = 0;for(intx = e; x < e + 3; x++)for(inty = f; y < f + 3; y++)if(b[x][y]>0)temp2 ++;if(temp1 + temp2> max)max = temp1 + temp2;}}cout << max << endl;}}搞了好久终于明白这个题的意思了。他的意思是一个方格里可以有很多个蘑菇，但是用3*3数组扫描一次只能消除每个方格里的一个蘑菇，就是说扫描一次后原方格可能还有蘑菇。我的方法是先在大数组里选取3*3数组，求出蘑菇数，然后再在当前扫描后的大数组里再选3*3数组，求取蘑菇数，再求和比较。
编辑于 2016-01-04 23:03:45
回复(0)
暴力
先把蘑菇最多的九宫格清掉，再把蘑菇最多（相对于原始，蘑菇次多）的九宫格清掉
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)
/**
本菜鸡觉得很多楼都是用贪心思想做的，我不认同。如：
1 0 1 1 0 1
1 0 1 1 0 1
1 0 1 1 0 1
贪心只能得到9，而非正确答案12
因此本菜鸡写了另一种解法，但是复杂度有点高（加了两个剪枝条件）。如有不妥或者更好的方法，请大佬们尽情留言。
*/
本菜鸡觉得很多楼都是用贪心思想做的，我不认同。如：
1 0 1 1 0 1
1 0 1 1 0 1
1 0 1 1 0 1
贪心只能得到9，而非正确答案12
因此本菜鸡写了另一种解法，但是复杂度有点高（加了两个剪枝条件）。如有不妥或者更好的方法，请大佬们尽情留言。
*/
#include <bits/stdc++.h>
using namespace std;
struct Node {
int num;
int x, y;
Node(int num, int x, int y) : num(num), x(x), y(y) {}
};
bool cmp(Node* a, Node* b) {
if (a->num > b->num)
return true;
return false;
}
int main() {
int N, M, K;
while (cin >> N >> M >> K) {
vector<vector<int> > graph(N+2, vector<int>(M+2, 0));
using namespace std;
struct Node {
int num;
int x, y;
Node(int num, int x, int y) : num(num), x(x), y(y) {}
};
bool cmp(Node* a, Node* b) {
if (a->num > b->num)
return true;
return false;
}
int main() {
int N, M, K;
while (cin >> N >> M >> K) {
vector<vector<int> > graph(N+2, vector<int>(M+2, 0));
// 读入数据
for (int i = 0; i < K; ++i) {
int x, y;
cin >> x >> y;
++graph[x][y];
}
// 将每个3*3区域的蘑菇数算出来，新建Node对象
vector<Node*> m;
vector<int> dirs {-1, 0, 1};
for (int x = 1; x <= N; ++x) {
for (int y = 1; y <= M; ++y) {
int cnt = 0;
for (auto i: dirs)
for (auto j: dirs)
if (graph[x+i][y+j] > 0)
++cnt;
m.push_back(new Node(cnt, x, y));
}
}
for (int i = 0; i < K; ++i) {
int x, y;
cin >> x >> y;
++graph[x][y];
}
// 将每个3*3区域的蘑菇数算出来，新建Node对象
vector<Node*> m;
vector<int> dirs {-1, 0, 1};
for (int x = 1; x <= N; ++x) {
for (int y = 1; y <= M; ++y) {
int cnt = 0;
for (auto i: dirs)
for (auto j: dirs)
if (graph[x+i][y+j] > 0)
++cnt;
m.push_back(new Node(cnt, x, y));
}
}
// 对所有Node对象以蘑菇数进行从大到小排序
sort(m.begin(), m.end(), cmp);
sort(m.begin(), m.end(), cmp);
int ans = 0;
int size = (int)m.size();
// i,j是n2的复杂度遍历，每两个区域都要比较一次
for (int i = 0; i < size; ++i) {
int cnt1 = m[i]->num;
int x1 = m[i]->x, y1 = m[i]->y;
// 剪枝一：由于Node从大到小排列，所以当前Node->num * 2 <= ans则没必要继续找了
if (cnt1*2 <= ans)
break;
for (int j = i+1; j < size; ++j) {
int cnt2 = m[j]->num;
int x2 = m[j]->x, y2 = m[j]->y;
// 剪枝二：两个区域不考虑重叠区域数量为1的蘑菇，和小于ans则没有必要查看重叠部分了
if (cnt1 + cnt2 <= ans)
break;
int cnt = cnt1 + cnt2;
// 两个区域横，纵坐标差3及以上则不会有重叠区域，否则考虑重叠区域数量为1的蘑菇的数量
if (!(abs(x1-x2) >= 3 || abs(y1-y2) >= 3)) {
int k1 = x1, k2 = x2;
if (k1 > k2) swap(k1, k2);
int l1 = y1, l2 = y2;
if (l1 > l2) swap(l1, l2);
for (int k = k2-1; k <= k1+1; ++k)
for (int l = l2-1; l <= l1+1; ++l)
if (1 == graph[k][l])
--cnt;
}
ans = max(ans, cnt);
}
}
cout << ans << endl;
}
return 0;
}
int size = (int)m.size();
// i,j是n2的复杂度遍历，每两个区域都要比较一次
for (int i = 0; i < size; ++i) {
int cnt1 = m[i]->num;
int x1 = m[i]->x, y1 = m[i]->y;
// 剪枝一：由于Node从大到小排列，所以当前Node->num * 2 <= ans则没必要继续找了
if (cnt1*2 <= ans)
break;
for (int j = i+1; j < size; ++j) {
int cnt2 = m[j]->num;
int x2 = m[j]->x, y2 = m[j]->y;
// 剪枝二：两个区域不考虑重叠区域数量为1的蘑菇，和小于ans则没有必要查看重叠部分了
if (cnt1 + cnt2 <= ans)
break;
int cnt = cnt1 + cnt2;
// 两个区域横，纵坐标差3及以上则不会有重叠区域，否则考虑重叠区域数量为1的蘑菇的数量
if (!(abs(x1-x2) >= 3 || abs(y1-y2) >= 3)) {
int k1 = x1, k2 = x2;
if (k1 > k2) swap(k1, k2);
int l1 = y1, l2 = y2;
if (l1 > l2) swap(l1, l2);
for (int k = k2-1; k <= k1+1; ++k)
for (int l = l2-1; l <= l1+1; ++l)
if (1 == graph[k][l])
--cnt;
}
ans = max(ans, cnt);
}
}
cout << ans << endl;
}
return 0;
}
发表于 2019-09-13 22:51:03
回复(0)
package com.special.first;
import java.util.Scanner;
/**
* 网易02-扫描透镜
*
* 我用的动态规划的思想，节省不必要的计算
* 首先求出第一个3行3列的最大值，
* 然后求第二个时候可以看做减去第一列的所有的值和加上当前的列的所有值
* 故我们每一次都保留前一次的状态
* 扩展到矩阵中，每一次起一行的时候，只需把上一行的初始3行3列值拿来直接用
* 即减去上一个9宫的第一行和加上当前的行即可
*
* 这里坑很多，注意如果格子里的蘑菇很多，只能请理一个！
* 然后我们第一次选完后，要更新这个9宫，之后再求一次最大值即可
*
* 优化：我陷入了当行列小于3的时候无法自拔，所以添加了很多无关紧要的判断代码
* 所以我们可以设置矩阵大小的时候可以跟3比较啊，小于3的时候，就申请3行3列，空白格为0
* 不影响结果！！！
* Create by Special on 2018/3/11 16:34
*/
public class Pro064 {
public static int cleanMushrooms(int N, int M, int[][] mushrooms){
int indexR = 0, indexC = 0, max = 0, begin = 0, temp = 0;
int beginRow = N >= 3 ? 3 : N;
int beginCol = M >= 3 ? 3 : M;
for(int i = 0; i < beginRow; i++){
for(int j = 0; j < beginCol; j++){
if(mushrooms[i][j] > 0) {
begin++;
}
}
}
temp = begin;
max = Math.max(max, temp);
for(int j = 3; j < M; j++){
for(int i = 0; i < beginRow; i++){
temp = temp - (mushrooms[i][j - 3] > 0 ? 1 : 0)
+ (mushrooms[i][j] > 0 ? 1 : 0);
}
if(temp > max){
max = temp;
indexR = 0;
indexC = j - 2;
}
}
for(int i = 3; i < N; i++){
for(int j = 0; j < beginCol; j++){
begin = begin - (mushrooms[i - 3][j] > 0 ? 1 : 0)
+ (mushrooms[i][j] > 0 ? 1 : 0);
}
temp = begin;
if(temp > max){
max = temp;
indexR = i - 2;
indexC = 0;
}
for(int j = 3; j < M; j++){
for(int index = i - 2; index <= i; index++) {
temp = temp - (mushrooms[index][j - 3] > 0 ? 1 : 0)
+ (mushrooms[index][j] > 0 ? 1 : 0);
}
if(temp > max){
max = temp;
indexR = i - 2;
indexC = j - 2;
}
}
}
int result = max;
for(int i = indexR; i < Math.min(N, indexR + 3); i++){
for(int j = indexC; j < Math.min(M, indexC + 3); j++){
if(mushrooms[i][j] > 0){
mushrooms[i][j]--;
}
}
}
return result;
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while(input.hasNext()){
int N = input.nextInt();
int M = input.nextInt();
int K = input.nextInt();
int[][] mushrooms = new int[N][M];
while(K-- > 0){
mushrooms[input.nextInt() - 1][input.nextInt() - 1]++;
}
int result = 0;
result += cleanMushrooms(N, M, mushrooms);
result += cleanMushrooms(N, M, mushrooms);
System.out.println(result);
}
}
}
发表于 2018-03-11 20:17:33
回复(0)
#include <bits/stdc++.h>
using namespace std;
void Scan(vector<vector<int>> G, int N, int M, int result[])
{ for(int i=0;i<N-2;i++) for(int j=0;j<M-2;j++) { int t = 0; for(int p=i;p<i+3;p++) for(int q=j;q<j+3;q++) if(G[p][q]>0) t++; if(result[0]<t) { result[0] = t; result[1] = i; result[2] = j; } }
}
int main()
{ int N,M,K; int x,y; while(cin>>N>>M>>K) { if(N<3) N = 3; if(M<3) M = 3; vector<vector<int>> G(N,vector<int>(M,0)); while(K--) { cin>>x>>y; G[x-1][y-1]++; } int first[3] = {0}; int second[3] = {0}; Scan(G,N,M,first); for(int i=first[1];i<first[1]+3;i++) for(int j=first[2];j<first[2]+3;j++) if(G[i][j]>0) G[i][j]--; Scan(G,N,M,second); cout<<first[0]+second[0]<<endl; } return 0;
}
发表于 2017-12-19 01:14:37
回复(0)
//本题题意有点迷，这里解释下：大致就是N*M大小的草地，放置K个蘑菇，多个蘑菇可放在同一个格子里，每片透镜仅能使用一次，每次使用可使得以
探查点为中心的3*3大小的九宫格中，有蘑菇的格子中蘑菇数量减一，没有蘑菇的不清理，问题是现在有两片透镜，求最多能清理多少蘑菇
#include<iostream>
using namespace std;
int main()
{
int N, M, K;
const int LensCount = 2; //透镜数量
while (cin >> N >> M >> K)
{
int x, y;
int arr[21][21] = { 0 };
while (K--) //输入
{
cin >> x >> y;
arr[x][y]++;
}
/*cont记录每个九宫格中有蘑菇的格子数量，MAXC记录每片透镜所能清理的最大蘑菇数量也即cont的最大值，MAXP1,MAXP2分别记录最大cont所在的
位置（后面清理蘑菇时需要用到），RET保存所有被清理的蘑菇的数量也即最后结果*/
int i, j, k, cont, MAXC = 0, MAXP1, MAXP2, RET = 0;
for(k = 0; k < LensCount; k++)
{
for (i = 2; i < N; i++)
{
for (j = 2; j < M; j++)
{
cont = 0;
if (arr[i - 1][j - 1]) cont++;
if (arr[i - 1][j ]) cont++;
if (arr[i - 1][j + 1]) cont++;
if (arr[i ][j - 1]) cont++;
if (arr[i ][j ]) cont++;
if (arr[i ][j + 1]) cont++;
if (arr[i + 1][j - 1]) cont++;
if (arr[i + 1][j ]) cont++;
if (arr[i + 1][j + 1]) cont++;
if (cont > MAXC) { MAXC = cont; MAXP1 = i; MAXP2 = j; }
//保存当前透镜所能清理的最大蘑菇数量，并保存最大数量所在草地的位置
}
}
RET += MAXC; MAXC = 0;
//最后一片透镜无需清理九宫格，直接输出就可以了
if(k == LensCount - 1) { cout << RET << endl;
break; }
//除最后一片透镜外，找到最大值后都需要清理九宫格，以供下一片透镜使用
for (i = MAXP1 - 1; i <= MAXP1 + 1; i++)
for (j = MAXP2 - 1; j <= MAXP2 + 1; j++)
if (arr[i][j]) arr[i][j]--;
}
}
return 0;
}
发表于 2017-07-20 22:51:43
回复(0)
//好像也只有暴力求了吧
#include<iostream>
#include<vector>
using namespace std;
int main(){
int N, M, K;
while(cin>>N>>M>>K){
vector<vector<int>> input(N, vector<int>(M, 0));
for(int i = 0; i < K; ++i){
int x, y;
cin>>x>>y;
input[x-1][y-1]++;
}
int max1 = 0, max2 = 0;
int x, y;
for(int i = 0; i < N-2; ++i){
for(int j = 0; j < M-2; ++j){
int num = 0;
for(int t = i; t <= i+2; ++t){
for(int k = j; k <= j+2; ++k)
if(input[t][k]) num++;
}
if(num > max1){
max1 = num;
x = i; y = j;
}
}
}
for(int i = 0; i < N-2; ++i){
for(int j = 0; j < M-2; ++j){
int num = 0;
for(int t = i; t <= i+2; ++t){
for(int k = j; k <= j+2; ++k){
if(t >= x && t <= x+2 && k >= y && k <= y+2){
if(input[t][k] > 1) num++;
}
else if(input[t][k])
num++;
}
}
if(num > max2) max2 = num;
}
}
cout<<max1+max2<<endl;
}
return 0;
}
发表于 2017-06-30 14:40:21
回复(0)
#include <iostream>
using namespace std;
int main(){
int N, M, K;
while (cin >> N >> M >> K){
int map[30][30] = { 0 };
for (int i = 0; i < K; i++){//数据载入一个二维数组
int x, y;
cin >> x >> y;
map[x][y]++;
}
int sum = 0;
int max_i = 0;
int max_j = 0;
for (int i = 0; i < N - 1; i++){//遍历数组，记录一次最大可消除数量
for (int j = 0; j < M - 1; j++){
int temp;//可用函数代替计算九宫格，这里直接算了
temp = !map[i][j] + !map[i + 1][j] + !map[i + 2][j] + !map[i][j + 1] + !map[i + 1][j + 1] + !map[i + 2][j + 1] + !map[i][j + 2] + !map[i + 1][j + 2] + !map[i + 2][j + 2];
temp = 9 - temp;
if (temp > sum){//记录最大位置
sum = temp;
max_i = i;
max_j = j;
}
}
}
for (int i = max_i; i < max_i + 3; i++){
for (int j = max_j; j < max_j + 3; j++){//将第一遍消除的蘑菇减去
if(map[i][j] > 0)
--map[i][j];
}
}
int sum2 = 0;
for (int i = 0; i < N - 1; i++){//第二遍同理
for (int j = 0; j < M - 1; j++){
int temp;
temp = !map[i][j] + !map[i + 1][j] + !map[i + 2][j] + !map[i][j + 1] + !map[i + 1][j + 1] + !map[i + 2][j + 1] + !map[i][j + 2] + !map[i + 1][j + 2] + !map[i + 2][j + 2];
temp = 9 - temp;
if (temp > sum2)
sum2 = temp;
}
}
cout << sum + sum2 << endl;
}
}
发表于 2017-06-10 10:07:29
回复(0)
/*暴力枚举就好，刚开始也以为是简单的贪心算法，不应该的，暴力美学就好*/
#include<iostream>
#include<vector>
using namespace std;
int KKK(vector<vector<int>> f, int N, int M)
{
int max=0;
for (int i = 0; i < N - 2; i++)
{
for (int j = 0; j < M - 2; j++)
{
int temp = 0;
vector<vector<int>> count(f);
//左上角坐标为(i,j)的时候的3*3方阵中的蘑菇个数temp
for (int x = i; x < i + 3; x++)
{
for (int y = j; y < j + 3; y++)
{
if ((f[x][y] != 0)&&(count[x][y]!=0))
{
temp++;
count[x][y]--;
}
}
}
for (int a = 0; a < N - 2; a++)
{
for (int b = 0; b < M - 2; b++)
{
int temp2 = 0;
for (int k = a; k < a + 3; k++)
{
for (int l = b; l < b + 3; l++)
{
if (count[k][l]!=0)
{
temp2++;
if ((temp+temp2)>max)
{
max = temp+temp2;
}
}
}
}
}
}
}
}
return max;
}
int main()
{
int M, N, K;
int x, y;
while (cin >> N >> M >> K)
{
vector<vector<int>> f(N,
vector<int>(M,0)); //创建了一个N*M的二维向量
for (int i = 0; i < K; i++)
{
cin >> x >> y;
f[x-1][y-1]++;
}
int res=KKK(f, N, M);
cout << res << endl;
}
}
发表于 2017-04-15 18:10:30
回复(0)
// 讲真，这题目蛮神奇的，其实意思就是让你先遍历每一个点，把这个点当做(3*3)的起点开始扫描
// 统计每一个点作为起点时的9个方格中蘑菇的数目，并且保存数目，及起点的坐标，遍历完一遍后
// 将最多蘑菇数目保存，并且将最多蘑菇的起点开始，那9个点里的蘑菇数目-1，然后开始第二次扫描
import java.util.*;
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();
int[][] mush = new int[N][M];
int cnt = 0;
for(int i = 0; i < K; i++)
mush[in.nextInt() - 1][in.nextInt() - 1]++;
System.out.println(find(mush, N, M));
}
}
public static int find(int[][] mush, int N, int M){
int x = 0, y = 0, max = 0;
for(int i = 0; i < N - 2; i++){
for(int j = 0; j < M - 2; j++){
int tmp = 0;
for(int p = i; p < i + 3; p++){
for(int q = j; q < j + 3; q++){
if(mush[p][q] >= 1)
tmp++;
}
}
if(tmp > max){
max = tmp;
x = i;
y = j;
}
}
}
for(int p = x; p < x + 3; p++){
for(int q = y; q < y + 3; q++){
if(mush[p][q] >= 1)
mush[p][q]--;
}
}
int maxf = max;
max = 0;
for(int i = 0; i < N - 2; i++){
for(int j = 0; j < M - 2; j++){
int tmp = 0;
for(int p = i; p < i + 3; p++){
for(int q = j; q < j + 3; q++){
if(mush[p][q] >= 1)
tmp++;
}
}
if(tmp > max)
max = tmp;
}
}
return maxf + max;
}
}
发表于 2017-03-19 14:03:42
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-09-16 00:25:22 -
2022-09-10 18:17:53 -
2022-09-10 10:39:05
-
2022-09-06 13:17:35
-
2022-09-03 16:30:09
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
#include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> using namespace std; const int dx[] = {-1,-1,0,1,1,1,0,-1},dy[] = {0,1,1,1,0,-1,-1,-1}; int main(){ int n,m,k; while(scanf("%d%d%d",&n,&m,&k) != EOF){ int map[30][30]; int ret = 0; memset(map,0,sizeof(map)); for(int i = 0;i < k;++ i){ int x,y; scanf("%d%d",&x,&y); map[x - 1][y - 1] += 1; } for(int i = 0;i < n;++ i) for(int j = 0;j < m;++ j) for(int u = 0;u < n;++ u) for(int v = 0;v < m;++ v){ int cnt[30][30]; memset(cnt,0,sizeof(cnt)); int tmp = 0; ++ cnt[i][j]; if(map[i][j]) ++ tmp; for(int k = 0;k < 8;++ k){ int ex = dx[k] + i,ey = dy[k] + j; if(ex >= 0 && ex < n && ey >= 0 && ey < m && cnt[ex][ey] < map[ex][ey]) tmp += 1,cnt[ex][ey] += 1; } ++ cnt[u][v]; if(map[u][v] >= cnt[u][v]) ++ tmp; for(int k = 0;k < 8;++ k){ int ex = dx[k] + u,ey = dy[k] + v; if(ex >= 0 && ex < n && ey >= 0 && ey < m && map[ex][ey] > cnt[ex][ey]) tmp += 1,cnt[ex][ey] += 1; } if(tmp > ret) ret = tmp; } printf("%d\n",ret); } return 0; }