B - Dev, Please Add This!

思路:

对于每一个经过 '*' 的横线和竖线看成一个整体,设他们分别为分量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<bits/stdc++.h>
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<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#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 = , M = ;
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*], low[M*], cnt, stk[M*], top, cmp[M*], tot, n;
bool vis[M*];
vector<int> g[M*];
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 = ; i <= *n; ++i) if(!dfn[i]) tarjan(i);
for (int i = ; 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 = ; i <= n; ++i) scanf("%s", s[i]+);
for (int i = ; i <= n; ++i) {
for (int j = ; j <= m; ++j) {
if(s[i][j] == 'O') x = i, y = j;
if(s[i][j] != '#') {
if(j == || s[i][j-] == '#') st[++cnt] = {i, j};
id1[i][j] = cnt;
if(j == m || s[i][j+] == '#') ed[cnt] = {i, j};
}
}
}
for (int j = ; j <= m; ++j) {
for (int i = ; i <= n; ++i) {
if(s[i][j] != '#') {
if(i == || s[i-][j] == '#') st[++cnt] = {i, j};
id2[i][j] = cnt;
if(i == n || s[i+][j] == '#') ed[cnt] = {i, j};
}
}
}
two_sat::init(cnt);
for (int i = ; i <= cnt; ++i) {
ST = i;
dfs(ST);
}
for (int i = ; i <= cnt; ++i) if(!can[id1[x][y]][i] && !can[id2[x][y]][i]) two_sat::add(i, i+cnt);
for (int i = ; i <= cnt; ++i) {
for (int j = i+; 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 = ; i <= n; ++i) {
for (int j = ; 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 ;
}

最新文章

  1. 初来乍到 Java 和 .Net 迭代器功能
  2. Python之路(二)
  3. C/C++学习之路
  4. 用AJAX技术聚合RSS
  5. 新思路:Exception Handle
  6. mod_wsgi + pymssql通路SQL Server座
  7. JAVA优雅停机的实现
  8. WebPack错误集
  9. bzoj 2555: SubString
  10. web开发中遇到的乱码问题
  11. The Little Prince-12/14
  12. linux第三章学习笔记
  13. 028.Zabbix常见故障
  14. Centos6.5卸载图形化
  15. CentOS7图形界面启动报错unable to connect to X server
  16. wpf控件拖动
  17. Visual Studio 编译信息细度显示设置
  18. URL上的中文编码
  19. file中mkdirs和mkdir的区别-文件上传
  20. c++ STL stack容器成员函数

热门文章

  1. WordPress的摘要显示方式
  2. Direct2D 学习笔记 前言
  3. 【计算机视觉】OPENCV对于有alpha通道的透明背景图片的读取和图片叠加
  4. Codis的安装配置
  5. python 问题解决:UnicodeEncodeError: &#39;ascii&#39; codec can&#39;t encode character u&#39;\uff08&#39;
  6. Centos安装Python3及设置对应版本pip
  7. ActiveMQ Queue示例
  8. js 监听键盘的enter键
  9. win10系统ping另一台电脑上虚拟机的IP
  10. MySQL 多列排序