Code

#include <atcoder/modint>
#include <bits/stdc++.h>

using namespace atcoder;
using namespace std;

using mint = modint998244353;

const int green = '#';
const int red = '.';

vector<int> dx = {0, 0, 1, -1};
vector<int> dy = {1, -1, 0, 0};

class Graph {
  public:
    vector<string> mat;
    vector<vector<int>> cc;
    vector<vector<bool>> vis;
    int row, col;
    Graph(vector<string> &mat) {
        this->row = mat.size();
        this->col = mat[0].length();
        this->mat = mat;
        cc.resize(row, vector<int>(col, 0));
        vis.resize(row, vector<bool>(col, false));
    }

  public:
    bool valid(int x, int y) {
        if (x < 0 || x >= row || y < 0 || y >= col) {
            return false;
        }
        return true;
    }

    void dfs(int x, int y, int cc_id) {
        if (!valid(x, y) || mat[x][y] == red || vis[x][y]) {
            return;
        }

        vis[x][y] = true;
        cc[x][y] = cc_id;

        for (int dir = 0; dir < 4; dir++) {
            dfs(x + dx[dir], y + dy[dir], cc_id);
        }
    }
};

int solve(vector<string> &mat) {
    int row = mat.size();
    int col = mat[0].length();

    Graph g(mat);

    int cc_id = 0;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if (mat[i][j] == green && !g.vis[i][j]) {
                cc_id++;
                g.dfs(i, j, cc_id);
            }
        }
    }

    int total_cc = cc_id;
    int red_count = 0;
    mint ans = 0;

    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if (mat[i][j] == green) {
                continue;
            }

            set<int> adj_cc_count;
            for (int dir = 0; dir < 4; dir++) {
                int x = i + dx[dir];
                int y = j + dy[dir];
                if (g.valid(x, y) && mat[x][y] == green) {
                    adj_cc_count.insert(g.cc[x][y]);
                }
            }

            // Combine all adjacent connected components into a single one.
            int contrib = total_cc - (int)adj_cc_count.size();
            contrib += 1;
            ans += contrib;
            red_count += 1;
        }
    }

    ans /= red_count;
    return ans.val();
}

int main() {
    int row, col;
    cin >> row >> col;

    vector<string> mat;

    for (int i = 0; i < row; i++) {
        string str;
        cin >> str;
        mat.push_back(str);
    }

    cout << solve(mat) << "\n";
}