题解 | #牛客泡泡堂#

题意

在一个的矩阵中每个元素的数值都为0或1，放置一个长宽分别为与的十字，求十字覆盖元素和的最大值。
下文中代表玩家数量（）。
##18分做法：暴力
对于每一个点，暴力计算在这个点爆炸能炸死的人，代码如下

class Solution {
public:
    //bool isLegal(Point a,int i,int j,int xl,int xr){return a.x==i||a.y==j&&a.x>=xl&&a.x<=xr;}
    int BoomKill(int n, int m, vector<Point>& Player) {
                int maxAns=0;//存储最大答案
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                int ans=0;//存储在(i,j)位置放置炸弹的答案
                for(Point p : Player){
                    int xl= max(1,i-m+1),xr=min(n,i+m-1);
                    if(p.x==i||p.y==j&&p.x>=xl&&p.x<=xr)
                        ++ans;//如果能炸死答案就加一
                }
                if(ans>maxAns)maxAns=ans;
            }
        }
        return maxAns;
    }
};

时间复杂度：，共有三层循环。
空间复杂度：，为Player容器占用的空间。

100分做法