题解 | #Butterfly#

修补骑士一看见题面就放弃的差不多了。这里主要是绝大多数人可能会惯性思维的认为是从中间开始，之后往四边扩展验证，明显实现起来太过麻烦并且时间复杂度过大，不过考虑构造的思路是没有错的

对于每一个点，我们考虑积累三个元素：向上的延伸，向左上的延伸与向右上的延伸，对于一个方格（假设为右下角），我们先找到向上与向右最小的那一个，之后找到对应的右下角，之后就是右下角向上与向右最小的那一个，看能不能构建成一个封闭的蝴蝶形状。之所以能想到这个，是因为对于蝴蝶型就是由两个对角线与两条竖线决定的，我们只需要考虑到这四个元素就可以确定一个蝴蝶型（当然主要原因还是我看了题解.jpg）

思路有了大概的确定，我们打表又能发现两点：

1：只有一个X也算是蝴蝶型，并且是最小的蝴蝶型（顺带一提，这题目里的矩阵元素保证由X和O构成多半是假的，19号测试数据应该就是只有O，需要输出0）

2：蝴蝶型一定是个正方形，这主要是因为对角线X长度与边长X长度是一样导致的。同时必须要有中点也决定了这个正方形边长必须是奇数

修补骑士一开始来实现：

for(int r = 0;r < n;r++)
    {
        for(int p = 0;p < m;p++)
        {
            int downnum = 0;
             
            while(downnum + r < n)
            {
                if(themap[downnum + r][p] == 1)
                {
                    down[r][p]++;
                }
                else
                {
                    break;
                }
            }
             
            downnum = 0;
             
            while(downnum + r < n && downnum + p < m)
            {
                if(themap[downnum + r][p + downnum] == 1)
                {
                    rdown[r][p]++;
                }
                else
                {
                    break;
                }
            }
             
            while(downnum + r < n && p - downnum >= 0)
            {
                if(themap[downnum + r][p - downnum] == 1)
                {
                    ldown[r][p]++;
                }
                else
                {
                    break;
                }
            }
        }
    }

普普通通的扫描，可惜TLE了，这也是理所应当的，毕竟对于每个位次我们都进行了三次扫描操作。但是这实际上是可以优化的，也就是这里体现了动态规划思想

for(int r = 0;r < n;r++)
    {
        for(int p = 0;p < m;p++)
        {
            char t;
             
            cin>>t;
             
            if(t == 'X')
            {
                //单调方向怎么预处理一下呢，这下只有以下推上了
                if(r - 1 >= 0) down[r][p] = down[r - 1][p] + 1;
                else down[r][p] = 1;
                 
                if(r - 1 >= 0 && p - 1 >= 0) ldown[r][p] = ldown[r - 1][p - 1] + 1;
                else ldown[r][p] = 1;
                 
                if(r - 1 >= 0 && p + 1 < m) rdown[r][p] = rdown[r - 1][p + 1] + 1;
                else rdown[r][p] = 1;
            }
            else
            {
                down[r][p] = rdown[r][p] = ldown[r][p] = 0;
            }
        }
    }

这里也就是为什么修补骑士使用了向上方有多少个X记录而不是向下走（都可以做出来），主要是方便我们使用DP，对于初始状态我们更好处理。将其结合读入过程就差不多了

这里最普遍也是我看题解与绝大多数别人AC代码都是预处理完成后扫描一次，对于每个位置，我们找到向上走与向右上走的min后定义k，k为偶数就减1（上面说明了必须是个奇数边长的正方形），考虑到形成的蝴蝶型不一定充分利用了所有的X（可能有多余的），我们需要写一个循环来寻找有没有更小但是可以组成蝴蝶的取值（k-=2即可），之后维护max即可

AC代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
 
signed main() 
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
     
    int n,m;
     
    cin>>n>>m;
     
    vector<vector<int>> themap(n,vector<int>(m,0));
     
    vector<vector<int>> down(n,vector<int>(m,0));
    vector<vector<int>> ldown(n,vector<int>(m,0));
    vector<vector<int>> rdown(n,vector<int>(m,0));
  
    for(int r = 0;r < n;r++)
    {
        for(int p = 0;p < m;p++)
        {
            char t;
             
            cin>>t;
             
            if(t == 'X')
            {
                //单调方向怎么预处理一下呢，这下只有以下推上了
                if(r - 1 >= 0) down[r][p] = down[r - 1][p] + 1;
                else down[r][p] = 1;
                 
                if(r - 1 >= 0 && p - 1 >= 0) ldown[r][p] = ldown[r - 1][p - 1] + 1;
                else ldown[r][p] = 1;
                 
                if(r - 1 >= 0 && p + 1 < m) rdown[r][p] = rdown[r - 1][p + 1] + 1;
                else rdown[r][p] = 1;
            }
            else
            {
                down[r][p] = rdown[r][p] = ldown[r][p] = 0;
            }
        }
    }

    int maxk = 0;
     
    for(int r = 0;r < n;r++)
    {
        for(int p = 0;p < m;p++)
        {
            int k = min(down[r][p],rdown[r][p]);
             
            if(k % 2 == 0)
            {
                k--;//打表观察可得
            }          
             
            for(int q = k;q > maxk;q -= 2)
            //q > maxk是个很优秀但不是必要的剪枝，大概亏100ms
            //所以说我们平常在循环找最大值的情况下，对于明确小于的枝条我们就可以剪掉！
            
            //但感觉这个还是太吃熟练度了，唉，多练吧
            {  
                int sk = min(down[r][p + q - 1],ldown[r][p + q - 1]);     
                 
                if(sk < q)//这里也需要注意一下
                {
                    continue;
                }
                else
                {
                    maxk = q;
                     
                    break;
                }
            }
        }
    }
     
    cout<<maxk<<endl;
     
    return 0;
}

这是绝大多数人的做法也是绝对正确的做法，不过修补骑士一开始想的方法不一样：

对于可能的k取值（最大就是min(n,m)因为切正方形），我们把k搞成奇数后来扫描验证，因为已经有了k我们可以很轻松的找到右下角的位置是p + k - 1（这里不是点而是方格，也要注意）并进行验证，并且不用上一个方法那样k-=2不停验证，但是实际上这个方法很明显捡了西瓜丢了芝麻，会多次扫描全图，而原本正确方法就只需要扫一次

但我还是把这个方法写出来了，应该是正确的，就是果然后面的测试数据TLE了。或者说这个方法还可以优化？希望有大佬前来分析指正

//这个是TLE的代码哈，上面那个才是AC的
#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main() 
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int n,m;
    
    cin>>n>>m;
    
    vector<vector<int>> themap(n,vector<int>(m,0));
    
    vector<vector<int>> down(n,vector<int>(m,0));
    vector<vector<int>> ldown(n,vector<int>(m,0));
    vector<vector<int>> rdown(n,vector<int>(m,0));
   
    for(int r = 0;r < n;r++)
    {
        for(int p = 0;p < m;p++)
        {
            char t;
            
            cin>>t;
            
            if(t == 'X')
            {
                themap[r][p] = 1;

                if(r - 1 >= 0) down[r][p] = down[r - 1][p] + 1;
                else down[r][p] = 1;
                
                if(r - 1 >= 0 && p - 1 >= 0) ldown[r][p] = ldown[r - 1][p - 1] + 1;
                else ldown[r][p] = 1;
                
                if(r - 1 >= 0 && p + 1 < m) rdown[r][p] = rdown[r - 1][p + 1] + 1;
                else rdown[r][p] = 1;
            }
            else
            {
                themap[r][p] = 0;
                
                down[r][p] = rdown[r][p] = ldown[r][p] = 0;
            }
        }
    }
 
    int k = min(n,m);
    
    if(k % 2 == 0)
    {
        k--;
    }
    
    for(;k > 0;k -= 2)
    {
        for(int r = 0;r < n;r++)
        {
            for(int p = 0;p < m;p++)
            {
                if(p + k - 1 < m)
                {
                    if(themap[r][p + k - 1] == 0)
                    {
                        continue;
                    }
                    else
                    {
                        int min1 = min(down[r][p],rdown[r][p]);
                    
                        int min2 = min(down[r][p + k - 1],ldown[r][p + k - 1]);
                    
                        if(min(min1,min2) >= k)
                        {
                            cout<<k<<endl;
                        
                            return 0;
                        }
                        else
                        {
                            continue;
                        }
                    }
                }
                else
                {
                    continue;
                }
            }
        }
    }
    
    cout<<0<<endl;
    
    return 0;
}