P10719 WA#21求助 感谢了!!
查看原帖
P10719 WA#21求助 感谢了!!
1285551
UNDERTALE_RS楼主2024/7/10 22:15

改了很久,一直只错#21TAT

#include <iostream>
#include <cmath>
using namespace std;
long long n,m,k,a[105][105],qzh[105][105],minn= 1e8,cnt_1;
char q;

long long check(long long x,long long y){
    //check右边
    long long cnt = 0,ans = 1e9;
    for(int i = x;i <= n;i++){
        for(int j = y;j <= m;j++){
            if((abs(x-i)+1) * (abs(y-j)+1) < ans&&qzh[i][j]-qzh[x-1][j]-qzh[i][y-1]+qzh[x-1][y-1] >= k){
                ans = (abs(x-i)+1) * (abs(y-j)+1);
                cnt = qzh[i][j]-qzh[x-1][j]-qzh[i][y-1]+qzh[x-1][y-1];
                break;
            }
        }
    }
    //check左边
    for(int i = x;i <= n;i++){
        for(int j = 1;j < y;j++){
            if((abs(x-i)+1) * (abs(y-j)+1) < ans&&qzh[i][y]-qzh[x-1][y]-qzh[i][j-1]+qzh[x-1][j-1] >= k){
                ans = (abs(x-i)+1) * (abs(y-j)+1);
                cnt = qzh[i][y]-qzh[x-1][y]-qzh[i][j-1]+qzh[x-1][j-1];
                break;
            }
        }
    }
    if(cnt >= k)return ans;
    else return minn;
}

int main(){
    cin >> n >> m >> k;getchar();
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            scanf("%c",&q);
            a[i][j] = q-'0';
            if(a[i][j] >= 1)cnt_1++;
            qzh[i][j] = qzh[i-1][j]+qzh[i][j-1]-qzh[i-1][j-1]+a[i][j];
        }
        getchar();
    }
    if(cnt_1 < k){
        cout << 0 << endl;
        return 0;
    }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            if(a[i][j] == 1){
                minn = min(minn,check(i,j));
            }
        }
       
    }
    if(minn == 1e8){
        cout << 0 << endl;
        return 0;
    }
    cout << minn << endl;
    return 0;
}
                        
2024/7/10 22:15
加载中...