40分,#123458 - Time limited exceeded。 求调。
查看原帖
40分,#123458 - Time limited exceeded。 求调。
1777905
CrazyCarrot楼主2025/7/25 15:53
#include <iostream>
#include <vector>
#include <map>
using namespace std;

const int di[4] = {-1, 1, 0, 0};
const int dj[4] = {0, 0, -1, 1};

void updates(map<pair<int, int>,int>& smap,int i, int j, int n, int m){
    smap[{i,j}]++;
    for (int k = 0; k < 4; k++) {
        int ni = i + di[k], nj = j + dj[k];
        if (ni >= 0 && ni < n && nj >= 0 && nj < m)
            smap[{ni,nj}]++;
    }
}

bool checkfield(vector<string> a, int i, int j, int n, int m){
    for (int k = 0; k < 4; k++) {
        int ni = i + di[k], nj = j + dj[k];
        if (ni >= 0 && ni < n && nj >= 0 && nj < m && a[ni][nj] == '#'){
            return false;
        }
    }
    return true;
};

int main(){
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    map<pair<int, int>,int> smap;
    int sum = 0;
    int maxcount = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        for(int j = 0; j < m; j++){
            if(a[i][j] == '#'){
                updates(smap, i, j, n, m);
            }
        }
    }
;
    for(int i = 0;i < n; i++){
        for(int j = 0; j < m; j++){
            if(a[i][j] == '.')
                sum += checkfield(a,i,j,n,m);
            else {
                int count = 0;
                if(smap[{i,j}] == 1)
                    count++;
                for (int k = 0; k < 4; k++) {
                    int ni = i + di[k], nj = j + dj[k];
                    if (smap[{ni,nj}] == 1 )
                        count++; 
                }
                if(count > maxcount){
                    maxcount = count;
                }
            }
        }
    }
    
    cout << sum + maxcount << endl;
    return 0;
}
2025/7/25 15:53
加载中...