CF173B Chamber of Secrets

· · 题解

原题链接

这道题算法(BFS)难度不大，思维难度较高，是一道比较好的思维题。

当一根柱子被施了魔法，一条光线经过的时候实际效果是该行该列都会有光线。这即是说，一根柱子是否施了魔法影响的是该行该列是否有光线。

基于这一点，我们可以看作一根柱子连接了两个点——它处于的行和列，对这个柱子施魔法相当于花代价 1 连通了该行和该列。

剩下来的就很好想了，将 1 到 n 行编号 1 \sim n，将 1 到 n 列编号 n+1 \sim 2*n，从 1 到 n 跑一遍 BFS。

代码如下

#include<iostream>
#include<stdio.h>
using namespace std;
const int N=1e3+5,inf=0x7fffffff;
int n,m,q[N<<1],d[N<<1],mark[N<<1];
int tot,head[N<<1],Next[N*N<<2],vet[N*N<<2];
char g[N][N];
void add(int a,int b)
{
    Next[++tot]=head[a];
    vet[tot]=b;
    head[a]=tot;//邻接表存边 
}
void bfs()
{
    for(int i=1;i<=n+m;i++)  d[i]=inf;//初始化为最大值
    int le=0,ri=0;
    d[1]=0,q[++ri]=1,mark[1]=1;
    while(le<ri)//BFS
    {
        int x=q[++le];
        for(int i=head[x];i;i=Next[i])
        {
            int y=vet[i];
            if(mark[y]) continue;
            d[y]=d[x]+1;
            q[++ri]=y; mark[y]=1;
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",g[i]+1);//直接读入一整行字符串再处理
        for(int j=1;j<=m;j++)
            if(g[i][j]=='#')  add(i,j+n),add(j+n,i);
    }
    bfs();
    if(d[n]==inf)  printf("-1");
    else  printf("%d",d[n]);
return 0;
}