CF1214D Treasure Island

· · 题解

这题真的坑……

就这样，我看着机房里的其他同学一个一个在最后几分钟绝杀这道题，然后再看着他们一个一个FST……

首先，我们可以发现，答案肯定不会超过2。因为如果我们把(1,2),(2,1)这两个点堵上，或者把(n-1,m),(n,m-1)赌上，都可以保证走不到终点。

所以，我们可以分类讨论三种答案：

1、0

只要刚开始就走不到终点，答案就是0，记录一个f数组，表示每个点是否能走到，那么f[i][j]=f[i-1][j]|f[i][j-1]。

2、1

如何判断只堵一个点就能使Vasya走不到终点呢？

我们把整个矩阵想象成一个图，(i,j)向(i,j+1),(i+1,j)连边，就可以构成一个DAG。如果这是无向图，那么我们要找的点就是割点。

对于有向图呢？有向图必经点！

然而这是一个DAG，我们直接可以用hash+路径条数去求必经点。

然而，本题恶意卡hash，我们机房里几个写hash的同学全部FST了……

还有种解决方法是支配树，不过那个没多少人会……而且非常麻烦……

我们得充分挖掘本题的性质，发现有一个这样的性质：

..#.
.#..
#...
....

如果有一条这样的对角线上的每一个点都是'#'，就无法到达终点。

于是，如果有一条对角线上只有一个'.'，那么这个点就是必经点……吗？

我考场上就这么打了，就这么WA了。

考虑如下情况：

.#..
#...
..#.
.#..

那么(2,4)就不是必经边了，因为从起点出发根本到不了……

那么再用f数组判断一下能否到达这个点就好了……吗？

我也这么打了，也WA了……

再考虑一个情况：

..#
.#.
.#.

那么(3,1)也不是必经点了，因为从它根本到不了终点……

于是，我们再开一个数组g，表示每个点出发是否能到达终点。

结论：如果存在一条对角线上只有一个'.'，且这个点能从起点到达它再到达终点，那么它就是必经点。

3、2

排除了其它情况，答案就是2了。

注意事项：本题的范围是3≤n*m≤1000000，我们不能开二维数组，我开了一个一维数组，事实上vector也可以。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define res register int
#define ll long long
//#define cccgift
//#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
//char buf[1<<21],*p1=buf,*p2=buf;
namespace wode{
    template<typename T>
    inline void read(T &x)
    {
        static char ch;bool f=1;
        for(x=0,ch=getchar();!isdigit(ch);ch=getchar()) if(ch=='-') f=0;
        for(;isdigit(ch);x=(x<<1)+(x<<3)+(ch^48),ch=getchar());x=f?x:-x;
    }
    template<typename T>
    void print(T x)
    {
        if (x<0) putchar('-'),x=-x;
        if (x>=10) print(x/10);
        putchar(x%10+'0');
    }
    template<typename T>
    inline void print(T x,char ap) {print(x);if (ap) putchar(ap);}
    template<typename T>
    inline T max(T x,T y) {return x<y?y:x;}
    template<typename T>
    inline T min(T x,T y) {return x<y?x:y;}
    template<typename T>
    inline void chkmax(T &x,T y) {x=x<y?y:x;}
    template<typename T>
    inline void chkmin(T &x,T y) {x=x<y?x:y;}
}
using wode::read;using wode::chkmin;using wode::chkmax;using wode::print;
int n,m,d[2000001];
bool f[1000001],g[1000001];
char s[1000001];
inline int getid(int x,int y) {
    if(x<1||y<1||x>n||y>m) return 0;
    return (x-1)*m+y;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(res i=1;i<=n;++i)
      for(res j=1;j<=m;++j) cin>>s[getid(i,j)];
    f[1]=true;
    for(res i=1;i<=n;++i)
      for(res j=1;j<=m;++j) if(s[getid(i,j)]=='.'&&(i>1||j>1)) f[getid(i,j)]|=f[getid(i-1,j)]|f[getid(i,j-1)];
    if(!f[n*m]) return cout<<0<<endl,0;
    g[n*m]=true;
    for(res i=n;i;--i)
      for(res j=m;j;--j) if(s[getid(i,j)]=='.'&&(i<n||j<m)) g[getid(i,j)]|=g[getid(i+1,j)]|g[getid(i,j+1)];
    for(res i=1;i<=n;++i)
      for(res j=1;j<=m;++j) if(f[getid(i,j)]&&g[getid(i,j)]) ++d[i+j]; //判断对角线
    for(res i=3;i<n+m;++i) if(d[i]==1) return cout<<1<<endl,0; //注意起点和终点的那条对角线不能算！
    cout<<2<<'\n';
    cout<<flush;
    return 0;
}