2 条题解

  • 0
    @ 2025-9-23 15:30:17
    #include <iostream>
    #include <vector>
    #include <string>
    using namespace std;
    inline bool in(int x, int y, int n, int m) {
        return x >= 0 && x < n && y >= 0 && y < m;
    }
    inline bool good(const vector<string>& g, int x, int y, int n, int m) {
        const int d[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
        for (int i = 0; i < 4; i++) {
            int nx = x + d[i][0], ny = y + d[i][1];
            if (in(nx, ny, n, m) && g[nx][ny] == '#')
                return false;
        }
        return true;
    }
    inline bool goodAfter(const vector<string>& g, int x, int y, int cx, int cy, int n, int m) {
        const int d[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
        for (int i = 0; i < 4; i++) {
            int nx = x + d[i][0], ny = y + d[i][1];
            if ((nx == cx && ny == cy) || !in(nx, ny, n, m))
                continue;
            if (g[nx][ny] == '#')
                return false;
        }
        return true;
    }
    
    int main() {
        int n, m;
        cin >> n >> m;
        vector<string> g(n);
        for (int i = 0; i < n; i++) cin >> g[i];
        int orig = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (g[i][j] == '.' && good(g, i, j, n, m))
                    orig++;
        
        int maxAdd = 0;
        const int d[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == '#') {
                    int add = 0;
                    if (goodAfter(g, i, j, i, j, n, m)) add++;
                    for (int k = 0; k < 4; k++) {
                        int x = i + d[k][0], y = j + d[k][1];
                        if (in(x, y, n, m) && g[x][y] == '.') {
                            if (!good(g, x, y, n, m) && goodAfter(g, x, y, i, j, n, m))
                                add++;
                        }
                    }
                    maxAdd = max(maxAdd, add);
                }
            }
        }
        
        cout << orig + maxAdd << endl;
        return 0;
    }
        
    
    

    信息

    ID
    3314
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    递交数
    93
    已通过
    15
    上传者