WY5. 扫描透镜
描述
在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)处提莫种了一个蘑菇. 一个方格可以种无穷个蘑菇.输出描述
输出一行,在这一行输出一个整数,代表兰博最多可以清理多少个蘑菇.C 解法, 执行用时: 1ms, 内存消耗: 368KB, 提交时间: 2020-08-07
#include<stdio.h>
int scan(int turf[][20],int n,int m){
int i,j,num,p,q,max,x,y;
for(max=0,i=0;i<n-2;i++){
for(j=0;j<m-2;j++){
for(num=0,p=i;p<=i+2;p++){
for(q=j;q<=j+2;q++){
if(turf[p][q]>0)num++;
}
}
if(num>max){
max=num,x=i,y=j;
}
}
}
for(i=x;i<=x+2;i++){
for(j=y;j<=y+2;j++){
if(turf[i][j]>0)turf[i][j]--;
}
}
return max;
}
int main(){
int N,M,K,i,j;
int turf[20][20];
while(~scanf("%d%d%d",&N,&M,&K)){
if(M<3)M=3;
if(N<3)N=3;
for(i=0;i<N;i++){
for(j=0;j<M;j++)turf[i][j]=0;
}
while(K>0){
scanf("%d%d",&i,&j);
turf[i-1][j-1]++;
K--;
}
printf("%d\n",scan(turf,N,M)+scan(turf,N,M));
}
}
C++ 解法, 执行用时: 1ms, 内存消耗: 376KB, 提交时间: 2017-09-14
#include <bits/stdc++.h>
using namespace std;
#define MP make_pair
#define X first
#define Y second
#define forl(i, s, e) for (int i = s; i < e; i++)
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, M, K;
while (cin >> N >> M >> K) {
vector<vector<int>> matrix(N, vector<int>(M, 0));
forl(i, 0, K) {
int x, y;
cin >> x >> y;
matrix[x-1][y-1]++;
}
int total = 0;
int t = 2;
while (t--) {
int m = 0;
auto mi = MP(1, 1);
forl(i, 1, N-1) forl(j, 1, M-1) {
int s = 0;
forl(a, -1, 2) forl(b, -1, 2)
if (matrix[i+a][j+b])
s++;
if (s > m) {
m = s;
mi = MP(i, j);
}
}
total += m;
forl(a, -1, 2) forl(b, -1, 2)
matrix[mi.X+a][mi.Y+b] = max(0,
matrix[mi.X+a][mi.Y+b] - 1);
}
cout << total << '\n';
}
return 0;
}
C 解法, 执行用时: 2ms, 内存消耗: 372KB, 提交时间: 2018-09-12
#include<stdio.h>
int scan(int turf[][20],int n,int m){
int i,j,num,p,q,max,x,y;
for(max=0,i=0;i<n-2;i++){
for(j=0;j<m-2;j++){
for(num=0,p=i;p<=i+2;p++){
for(q=j;q<=j+2;q++){
if(turf[p][q]>0)num++;
}
}
if(num>max){
max=num,x=i,y=j;
}
}
}
for(i=x;i<=x+2;i++){
for(j=y;j<=y+2;j++){
if(turf[i][j]>0)turf[i][j]--;
}
}
return max;
}
int main(){
int N,M,K,i,j;
int turf[20][20];
while(~scanf("%d%d%d",&N,&M,&K)){
if(M<3)M=3;
if(N<3)N=3;
for(i=0;i<N;i++){
for(j=0;j<M;j++)turf[i][j]=0;
}
while(K>0){
scanf("%d%d",&i,&j);
turf[i-1][j-1]++;
K--;
}
printf("%d\n",scan(turf,N,M)+scan(turf,N,M));
}
}
C 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-12-19
#include<stdio.h>
int scan(int turf[][20],int n,int m){
int i,j,num,p,q,max,x,y;
for(max=0,i=0;i<n-2;i++){
for(j=0;j<m-2;j++){
for(num=0,p=i;p<=i+2;p++){
for(q=j;q<=j+2;q++){
if(turf[p][q]>0)num++;
}
}
if(num>max){
max=num,x=i,y=j;
}
}
}
for(i=x;i<=x+2;i++){
for(j=y;j<=y+2;j++){
if(turf[i][j]>0)turf[i][j]--;
}
}
return max;
}
int main(){
int N,M,K,i,j;
int turf[20][20];
while(~scanf("%d%d%d",&N,&M,&K)){
if(M<3)M=3;
if(N<3)N=3;
for(i=0;i<N;i++){
for(j=0;j<M;j++)turf[i][j]=0;
}
while(K>0){
scanf("%d%d",&i,&j);
turf[i-1][j-1]++;
K--;
}
printf("%d\n",scan(turf,N,M)+scan(turf,N,M));
}
}
C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-11-22
#include<iostream>
#include<vector>
using namespace std;
int main(){
int N,M,K;
while(cin>>N>>M>>K){
vector<vector<int>> matrix=vector<vector<int>>(N+2,vector<int>(M+2,0));
for(int i=1;i<=K;i++){
int x,y;
cin>>x>>y;
matrix[x][y]++;
}
int result=0;
for(int k=0;k<=1;k++){
int maxlen=0,maxx=0,maxy=0;
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
int nowlen=0;
for(int a=-1;a<=1;a++)
for(int b=-1;b<=1;b++){
if(matrix[i+a][j+b]>0)
nowlen+=1;
}
if(nowlen>maxlen){
maxlen=nowlen;
maxx=i;
maxy=j;
}
}
}
result+=maxlen;
for(int a=-1;a<=1;a++)
for(int b=-1;b<=1;b++){
if(matrix[maxx+a][maxy+b]>0)
matrix[maxx+a][maxy+b]--;
}
}
cout<<result<<endl;
}
}