题解 P2733 【家的范围 Home on the Range】

Khan_ · 2018-02-19 19:11:36 · 题解

矩阵DP,PJ蒟蒻首次题解（老师讲了一遍还是没有听懂，后来想了好久的说）。

用的是老师讲的方法，f[i][j]表示以i,j为右下角所能扩展的最大矩阵大小由于f[i][j]是由f[i-1][j],f[i-1][j-1]和f[i][j-1]决定的，所以方程为f[i][j]=min(f[i-1][j],f[i-1][j-1]),f[i][j-1])
代码见下：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAX=300;
const int INF=0X3F3F3F3F;
int n;
char map[MAX][MAX];
int num[MAX*MAX];//用桶排进行存储，num[i]表示第i大的矩阵有num[i]个 
int f[MAX][MAX];//表示以map[i][j]为右下角的矩阵的最大值 
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    cin>>map[i];
    /*---考虑边界情况---*/ 
    for(int i=0;i<n;i++)
    f[i][0]=(map[i][0]=='1');
    for(int j=0;j<n;j++)
    f[0][j]=(map[0][j]=='1');
    /*---全矩阵扫进行DP---*/
    for(int i=1;i<n;i++)
        for(int j=1;j<n;j++)
        if(map[i][j]=='1')//当前这个点不是障碍
        {
            f[i][j]=min(min(f[i-1][j],f[i][j-1]),f[i-1][j-1])+1;
            num[f[i][j]]++;
        }
    /*---统计全部个数（实现方式有点像斐波那契数列）---*/
    for(int i=n;i>0;i--)
    num[i-1]+=num[i];
    /*---输出结束---*/
    for(int i=2;i<=n;i++)
    if(num[i])
    cout<<i<<' '<<num[i]<<endl;      
}