题目描述:
shibowen和ganggang正在玩红警,可不料shibowen造出了核弹正要发射......(ganggang @_@) 已知核弹的攻击范围是边长n的正方形,ganggang的基地是边长m的正方形 基地样例:
...#.# .#...# ##...# ...... ..#### .#....
#表示房屋,.表示平地,求核弹最多能摧毁多少房屋(被核弹攻击的房屋都会消失,好强啊~~~~~~~)。
输入格式:
第一行基地边长m(10000>m>0) 第二行核弹攻击边长n(10000>n>-1) 接下来m行输入基地
输出格式:
摧毁最多房屋数
样例输入:
6
3
...#.#
######
......
......
#.....
...###
样例输出:
5
解题思路:
可以用搜索去解这道题,不过仔细看了看题,我感觉可以直接暴力四重循环就可以AC了,并没有超时。。。
程序代码:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char a[10001][10001];
int n,m;
int main()
{
int ans=0,num;
cin>>m>>n;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)
{
num=0;
for(int x=i;x<=i+n-1;x++)
{
for(int y=j;y<=j+n-1;y++)
{
if(a[x][y]=='#')
num++;
if(num>ans)
ans=num;
}
}
}
}
cout<<ans<<endl;
return 0;
}