CF173B Chamber of Secrets 题解

题目链接：CF173B Chamber of Secrets

题意：

“密室再次被打开了。”——这个消息传遍了霍格沃茨，而一些学生因为看到蛇怪而被石化。虽然邓布利多被迫离开了学校，但哈利正尝试进入密室。而这对伏地魔可不是什么好消息。他不希望任何人进入密室。因为他正在吸取金妮的灵魂。

密室是一个$n×m$的矩形网格，其中一些单元格有柱子。光线（蛇怪的凝视）可以穿过柱子而不改变方向。但是通过一些魔咒，我们可以让柱子在接收光线时反射所有光线向四个方向射去。如下图所示。

左边光线穿过没有施魔法的柱子，右边光线穿过施魔法的柱子，效果如图。蛇怪在密室的右下角，向左边凝视。据传说，直接看见蛇怪的眼睛就会马上死亡，而看到通过柱子的反射光线就会被石化。我们知道，密室的入口在左上角，而进入的人必须注视他所要移动的方向。图片就是第一个样例。

给定密室的大小，和普通柱子的位置，伏地魔想要让你对最少的柱子施法，使所有人不能进入密室；或者表示不能完成保护密室的任务。

输入格式：

输入的第一行包含两个整数$n$和$m$ $(2<=N,M<=1000)$接下来$n$行每行包含$m$个字符。每个字符都是”.”或”#”。表示密室的一个单元格。如果为”.”表示为空，如果为”#”表示有柱子。

输出格式：

输出所需要施法的柱子在最小值，如果不可能完成，则输出”$-1$”。

说明：

图片为样例解释，将两根柱子都施魔法才可以阻止哈利进入密室。

施法可以认为是把「列/行中没有光线的」连通，我们可以认为这是一个加边的过程

我们可以把行列看作节点 $1\sim n$ 和 $(n+1)\sim 2n$ ，然后跑一个 01bfs

时间复杂度 $\mathcal{O}(n^2)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e3 + 15))

char s[N],vis[N]; int n,m,pos=1,d[N],head[N];
struct Edge { int u,v,next; } e[N * N];
void addEdge(int u,int v) { 
    e[++pos] = {u,v,head[u]}; head[u] = pos;
}
int Why_does_cxy_have_a_girl_friend_qnq()
{
    for(int i = 1; i <= n + m; i++) d[i] = INF;
    queue<int> q; d[1] = 0; q.emplace(1); vis[1] = true;
    for(int u,v; !q.empty(); )
    {
        u = q.front(); q.pop();
        for(int i = head[u]; i; i = e[i].next)
        {
            v = e[i].v; if(vis[v]) continue;
            d[v] = d[u] + 1; q.emplace(v); vis[v] = true;
        }
    }
    return (d[n] == INF) ? (-1) : d[n];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> (s + 1);
        for(int j = 1; j <= m; j++)
            if(s[j] == '#') { addEdge(i, j + n), addEdge(j + n, i); }
    }
    cout << Why_does_cxy_have_a_girl_friend_qnq() << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/E-O-T-G-K/cf173b-chamber-of-secrets