P8033题解

· · 题解

题目大意：

给你一个由 R \times S 组成的字符方阵，让你找到一个 K \times K 的正方形使得其中 * 字符尽可能多，并输出这个区域在方阵中的位置

思路：

首先来看，这道题主要分两步来写，分别是算出数量和输出方阵。

本题数据范围较小， 3 \leq K \leq R,S \leq 100 。对于算数来说，直接暴力就可以过。

用 i 和 j 两个变量枚举这个区域的右下角，再用 x_1 和 x_2 两个变量算出能覆盖多少个，最后找到最大值并输出就行了。本区域就不详细讲解了

在输出最大值之后，我们还需要输出一个具体方案。我的方法比较笨一些，就是再算一遍，如果现在 * 的个数正好等于最大值，就证明现在的这个情况是最优解，我们就要输出具体方案。

首先，我们是要输出整个方阵的，这一步难就难在怎么判断是否是方框边缘的情况。我们把左上角的那个点坐标标记为 (a,b)，右下角的标记为 (c,d)，已知输出的符号只会有 3 种，接下来就要分类讨论了。

  1. + 符号。这种符号比较好判断，如果当前点 (x,y) 等于 (a,b)、 (c,d)、 (a,d) 或 (c,b)，我们就应该输出 + 。

  2. - 符号，如果当前点和 (a,b) 或 (c,d) 在同一行上且在区域内，就该输出 - 。

  3. | 符号，如果当前点和 (a,b) 或 (c,d) 在同一列上且在区域内，就该输出 | 。

剩下的就没了

代码

#include <iostream>
using namespace std;
typedef long long l;
char arr[105][105];
bool cmp(l x,l y,l x1,l y1){
    return ((x==x1) && (y==y1));
}
bool cmp2(l x,l y,l x1,l y1){
    return ((x==x1) || (y==y1));
}
//定义两个用于比较的函数，用于比较点之间的关系。
int main(){
    l r,s,k;
    cin>>r>>s>>k;
    for(l i=0;i<r;i++){
        for(l j=0;j<s;j++){
            cin>>arr[i][j];//输入
        }
    }
    l n=0;
    for(l i=k-2+1;i<r;i++){
        for(l j=k-2+1;j<s;j++){
            l x=0;
            for(l x1=i-(k-2);x1<i;x1++){
                for(l x2=j-(k-2);x2<j;x2++){
                    if(arr[x1][x2]=='*'){
                        x++;
                    }
                }
            }
            n=max(n,x);
            //暴力枚举求最值
        }
    }
    cout<<n<<endl;
    for(l i=k-2+1;i<r;i++){
        for(l j=k-2+1;j<s;j++){
        //再算一遍，看是否要输出
            l x=0;
            for(l x1=i-(k-2);x1<i;x1++){
                for(l x2=j-(k-2);x2<j;x2++){
                    if(arr[x1][x2]=='*'){
                        x++;
                    }
                }
            }
            if(x==n){//若等于，要输出
                for(l x1=0;x1<r;x1++){
                    for(l x2=0;x2<s;x2++){
                        if(cmp(x1,x2,i,j) || cmp(x1,x2,i-(k-1),j-(k-1)) || cmp(x1,x2,i,j-(k-1)) || cmp(x1,x2,i-(k-1),j)){
                            //判断是否输出'+'
                            cout<<"+";
                        }else if((cmp2(x1,x2,i,j) || cmp2(x1,x2,i-(k-1),j-(k-1))) && (x1<=i && x2 <= j && x1 >= i-(k-1) && x2 >=(j-(k-1)))){
                            if(x1==i || x1==i-(k-1)){
                                //判断是否输出'-'
                                cout<<"-";
                            }else{
                                //否则输出'|'
                                cout<<"|";
                            }
                        }else{
                            //如果不用输出符号的话，直接输出此位置的字符。
                            cout << arr[x1][x2];
                        }
                    }
                    cout<<endl;
                }
                //输出完了就结束程序
                return 0;
            }
        }
    }
    return 0;
}

完结撒花