30求调,有调必关
查看原帖
30求调,有调必关
1647691
songshufei楼主2025/6/22 10:21
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> grid(n);
    for (int i = 0; i < n; ++i) {
        cin >> grid[i];
    }

    // 预处理up, down, left, right数组
    vector<vector<int> > up(n, vector<int>(m, 0));
    vector<vector<int> > down(n, vector<int>(m, 0));
    vector<vector<int> > left(n, vector<int>(m, 0));
    vector<vector<int> > right(n, vector<int>(m, 0));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == '.') {
                left[i][j] = (j > 0) ? left[i][j-1] + 1 : 1;
            } else {
                left[i][j] = 0;
            }
        }
        for (int j = m-1; j >= 0; --j) {
            if (grid[i][j] == '.') {
                right[i][j] = (j < m-1) ? right[i][j+1] + 1 : 1;
            } else {
                right[i][j] = 0;
            }
        }
    }

    for (int j = 0; j < m; ++j) {
        for (int i = 0; i < n; ++i) {
            if (grid[i][j] == '.') {
                up[i][j] = (i > 0) ? up[i-1][j] + 1 : 1;
            } else {
                up[i][j] = 0;
            }
        }
        for (int i = n-1; i >= 0; --i) {
            if (grid[i][j] == '.') {
                down[i][j] = (i < n-1) ? down[i+1][j] + 1 : 1;
            } else {
                down[i][j] = 0;
            }
        }
    }

    // 计算原始可开垦的荒地数
    int original = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == '.') {
                int u = (i > 0) ? up[i][j] - 1 : 0;
                int d = (i < n-1) ? down[i][j] - 1 : 0;
                int l = (j > 0) ? left[i][j] - 1 : 0;
                int r = (j < m-1) ? right[i][j] - 1 : 0;
                if (u >= 1 && d >= 1 && l >= 1 && r >= 1) {
                    original++;
                }
            }
        }
    }

    int max_add = 0;

    // 定义八个方向的偏移量,用于检查周围的点
    int dirs[8][2] = {
        {-1, -1}, {-1, 0}, {-1, 1},
        {0, -1},          {0, 1},
        {1, -1},  {1, 0}, {1, 1}
    };

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == '#') {
                int current = 0;
                // 检查当前位置(i,j)清除后的情况
                int u = (i > 0) ? up[i][j] : 0;
                int d = (i < n-1) ? down[i][j] : 0;
                int l = (j > 0) ? left[i][j] : 0;
                int r = (j < m-1) ? right[i][j] : 0;

                if (u >= 1 && d >= 1 && l >= 1 && r >= 1) {
                    current++;
                }

                // 检查周围八个方向的点
                for (int k = 0; k < 8; ++k) {
                    int dx = dirs[k][0];
                    int dy = dirs[k][1];
                    int x = i + dx;
                    int y = j + dy;
                    if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == '.') {
                        bool up_ok = (x == 0) || (grid[x-1][y] == '.' || (x-1 == i && y == j));
                        bool down_ok = (x == n-1) || (grid[x+1][y] == '.' || (x+1 == i && y == j));
                        bool left_ok = (y == 0) || (grid[x][y-1] == '.' || (x == i && y-1 == j));
                        bool right_ok = (y == m-1) || (grid[x][y+1] == '.' || (x == i && y+1 == j));

                        if (up_ok && down_ok && left_ok && right_ok) {
                            current++;
                        }
                    }
                }

                if (current > max_add) {
                    max_add = current;
                }
            }
        }
    }

    cout << original + max_add << endl;
    return 0;
}
2025/6/22 10:21
加载中...