自动搬运

查看原文

来自洛谷，原作者为

	AmaZingFantasy AFOed

搬运于2025-08-24 22:35:20，当前版本为作者最后更新于2022-01-13 15:39:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意：

给你一个由 $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;
}

完结撒花