牛客练习赛1-A-矩阵题解

太过爱你忘了你带给我的痛 2022-12-28 11:17 141阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  输入描述
     *  输出描述
     *  输入
     *  输出
     *  备注
 *  算法分析
 *  解题代码
 *  错题总结

--------------------

链接：https://ac.nowcoder.com/acm/contest/2/A  
来源：牛客网

# 题目描述 #

给出一个**n \* m**的矩阵。让你从中发现一个最大的正方形。使得这样子的正方形在矩阵中出现了至少两次。输出最大正方形的边长。

## 输入描述 ##

> 第一行两个整数**n, m**代表矩阵的长和宽；  
> 接下来**n**行，每行**m**个字符（小写字母），表示矩阵；

## 输出描述 ##

> 输出一个整数表示满足条件的最大正方形的边长。

## 输入 ##

> 5 10
    ljkfghdfas
    isdfjksiye
    pgljkijlgp
    eyisdafdsi
    lnpglkfkjl

## 输出 ##

## 备注 ##

> 对于30%的数据，n,m≤100；  
> 对于100%的数据，n,m≤500；

# 算法分析 #

看到这题，我居然以为是暴力，还是太菜了

<table> 
 <tbody> 
  <tr> 
   <td><font>这道题的核心思想在于Hash + 二分</font> </td> 
  </tr> 
 </tbody> 
</table>

就是一道二维Hash的模版题目，关键在于二分正方形的边长。

# 解题代码 #

#include <iostream>
    #include <map>
    using namespace std;
    
    typedef unsigned long long ull;
    
    ull base1 = 131,base2 = 233;
    ull has[505][505];   //hash值存储
    ull p1[505],p2[505];    //p1为列的偏移值 p2为行的偏移值
    char mp[505][505];
    int n,m;
    map<ull, int> mmp;	//辅助记录这个正方形Hash值存在的个数
    
    //初始化Hash辅助数组
    void init()
    {
        
        p1[0] = 1;
        p2[0] = 1;
        for(int i = 1; i <= 505; i++){
        
            p1[i] = p1[i - 1] * base1;
            p2[i] = p2[i - 1] * base2;
        }
    }
    //初始化Hash辅助数组
    
    //对二维矩阵进行Hash变换
    void init_hash()
    {
        
        has[0][0] = 0;
        has[1][0] = 0;
        has[0][1] = 0;
        
        //对列进行hash
        for(int i = 1; i <= n; i++){
        
            for(int j = 1; j <= m; j++){
        
                has[i][j] = has[i][j - 1] * base1 + (mp[i][j] - 'a');
            }
        }
        
        //对行进行hash
        for(int i = 1; i <= n; i++){
        
            for(int j = 1; j <= m; j++){
        
                has[i][j] = has[i - 1][j] * base2 + has[i][j];
            }
        }
    }
    //对二维矩阵进行Hash变换
    
    //遍历寻找是否存在两个以上正方形相等
    int check(int x)
    {
        
        mmp.clear();	//每次要清理mmp中的数据
        for(int i = x; i <= n; i++)
            for(int j = x; j <= m; j++){
        
                ull k = has[i][j] - has[i - x][j] * p2[x] - has[i][j - x] * p1[x] + has[i - x][j - x] * p1[x] * p2[x];
                mmp[k]++;
                if(mmp[k] >= 2)
                    return 1;
            }
        return 0;
    }
    //遍历寻找是否存在两个以上正方形相等
    
    int main()
    {
        
        init();
        while(cin >> n >> m){
        
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= m; j++)
                    cin >> mp[i][j];
            
            init_hash();
            
          	//对正方形的边长进行二分。
          	//二分依据：
          	//如果小的正方形有两个以上相等，就去看比他大的有没有
          	//如果小的正方形没有两个以上相等，那么比这更大的也没有
            int l = 0, r = min(n, m);
            int ans = 0;
            int mid = (l + r + 1)/2;
            while(l < r)
            {
        
                mid = (l + r + 1)/2;
                if(check(mid)){
        
                    l = mid;
                    ans = mid;
                }
                else 
                    r = mid - 1;
            }
         	 	//对正方形的边长进行二分。
    
                cout << ans << endl;
            }
        
        return 0;
    }

--------------------

# 错题总结 #

[Hash算法][Hash]

[Hash]: http://codeblog-cy.top/2020/02/18/one-dimensional-two-dimensional-Hash-Algorithm/