Union-Find を使うことで \(O(HW \alpha(HW))\) で解くことができます。

前提として、上下左右に隣接していて、磁石が置かれてなく磁石に隣接していないマス同士は互いに行き来できます。そのようなマス同士を UF でつなぎます。

次に、UFを利用して、自分が属する連結成分のサイズを管理した配列を用意します(実装例と同様に cnt とします)。磁石が置かれてなく磁石が隣接してるマスについて、上下左右に隣接しているマスが磁石が置かれてなく磁石に隣接していないとき、そのマスが属する連結成分のリーダーの cnt を \(1\) 増やします。このとき、重複に注意です。

最後に cnt の最大値が答えとなります。

実装例

https://atcoder.jp/contests/abc351/submissions/52895274 (C++, 73 ms)

#include <bits/stdc++.h>
using namespace std;

#include <atcoder/dsu>
using namespace atcoder;

int main() {
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    for(int i = 0; i < h; i ++) cin >> s[i];
    dsu uf(h * w);
    int dy[4] = {-1, 0, 0, 1}, dx[4] = {0, -1, 1, 0};
    auto adj_mag = [&](int i, int j) -> bool {
        for(int k = 0; k < 4; k ++) {
            int y = i + dy[k], x = j + dx[k];
            if(y < 0 or y >= h or x < 0 or x >= w) continue;
            if(s[y][x] == '#') return true;
        }
        return false;
    };
    for(int i = 0; i < h; i ++) for(int j = 0; j < w; j ++) if(!adj_mag(i, j)) {
        if(i != h - 1 and !adj_mag(i + 1, j)) {
            uf.merge(i * w + j, (i + 1) * w + j);
        }
        if(j != w - 1 and !adj_mag(i, j + 1)) {
            uf.merge(i * w + j, i * w + j + 1);
        }
    }
    vector<int> cnt(h * w);
    for(int i = 0; i < h * w; i ++) cnt[i] = uf.size(i);
    for(int i = 0; i < h; i ++) for(int j = 0; j < w; j ++) {
        if(s[i][j] != '#' and adj_mag(i, j)) {
            set<int> st;
            for(int k = 0; k < 4; k ++) {
                int y = i + dy[k], x = j + dx[k];
                if(y < 0 or y >= h or x < 0 or x >= w) continue;
                if(s[y][x] == '#') continue;
                if(!adj_mag(y, x)) st.insert(uf.leader(y * w + x));
            }
            for(int e : st) cnt[e] ++;
        }
    }
    cout << *max_element(cnt.begin(), cnt.end()) << endl;
    return 0;
}