思路：

对于每一个经过 '*' 的横线和竖线看成一个整体，设他们分别为分量x和分量y

用2-sat考虑这个问题，

如果要经过 '*' ，那么x和y至少要有一个，即连边 !x -> y，!y -> x

如果对于某个分量a不能从通过 'O' 的分量到达它，那么连边 a -> !a

如果对于两个分量a、b，不能同时到达，那么连边a -> !b，b -> !a

然后用2-sat判断可不可行就可以了

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
     
      using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb emplace_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
      
       #define pli pair
       
        #define pii pair
        
         #define piii pair
         
          #define pdd pair
          
           #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//head const int N = 55, M = 2555;int n, m, ST, id1[N][N], id2[N][N], cnt, x, y;pii st[M], ed[M];bool can[M][M];char s[N][N];namespace two_sat { int dfn[M*2], low[M*2], cnt, stk[M*2], top, cmp[M*2], tot, n; bool vis[M*2]; vector
           
             g[M*2]; void init(int sz) { n = sz; } void add(int u, int v) { g[u].pb(v); } void tarjan(int u) { dfn[u] = low[u] = ++cnt; stk[++top] = u; vis[u] = true; for (int v : g[u]) { if(!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]); else if(vis[v]) low[u] = min(low[u], dfn[v]); } if(dfn[u] == low[u]) { cmp[u] = ++tot; while(stk[top] != u) cmp[stk[top]] = tot, vis[stk[top--]] = false; vis[stk[top--]] = false; } } bool ck() { for (int i = 1; i <= 2*n; ++i) if(!dfn[i]) tarjan(i); for (int i = 1; i <= n; ++i) { if(cmp[i] == cmp[i+n]) return false; } return true; }}void dfs(int u) { can[ST][u] = true; int v = id1[st[u].fi][st[u].se]^id2[st[u].fi][st[u].se]^u; if(!can[ST][v]) dfs(v); v = id1[ed[u].fi][ed[u].se]^id2[ed[u].fi][ed[u].se]^u; if(!can[ST][v]) dfs(v);}int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i) scanf("%s", s[i]+1); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if(s[i][j] == 'O') x = i, y = j; if(s[i][j] != '#') { if(j == 1 || s[i][j-1] == '#') st[++cnt] = {i, j}; id1[i][j] = cnt; if(j == m || s[i][j+1] == '#') ed[cnt] = {i, j}; } } } for (int j = 1; j <= m; ++j) { for (int i = 1; i <= n; ++i) { if(s[i][j] != '#') { if(i == 1 || s[i-1][j] == '#') st[++cnt] = {i, j}; id2[i][j] = cnt; if(i == n || s[i+1][j] == '#') ed[cnt] = {i, j}; } } } two_sat::init(cnt); for (int i = 1; i <= cnt; ++i) { ST = i; dfs(ST); } for (int i = 1; i <= cnt; ++i) if(!can[id1[x][y]][i] && !can[id2[x][y]][i]) two_sat::add(i, i+cnt); for (int i = 1; i <= cnt; ++i) { for (int j = i+1; j <= cnt; ++j) { if(!can[i][j] && !can[j][i]) two_sat::add(i, cnt+j), two_sat::add(j, cnt+i); } } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if(s[i][j] == '*') { two_sat::add(id1[i][j]+cnt, id2[i][j]); two_sat::add(id2[i][j]+cnt, id1[i][j]); } } } if(two_sat::ck()) printf("YES\n"); else printf("NO\n"); return 0;}