洛谷P2733 家的范围 题解 动态规划

题目链接:https://www.luogu.com.cn/problem/P2733

题目大意:
求一个 01矩阵 中由1构成的边长为2、3、4、……的矩阵的个数。

解题思路:
动态规划。
设状态 \(f[i][j]\) 表示以 \((i,j)\) 作为右下角的正方形的最大可能边长。
设坐标范围从 \(0\) 到 \(n-1\) ,则:

  • 当 \(i=0\) 或 \(j=0\) 时,
    • 若 \((i,j)\) 格子对应 '1' ,则 \(f[i][j] = 1\);
    • 否则, \(f[i][j] = 0\);
  • 否则,
    • 若 \((i,j)\) 格子对应 '1' ,则 \(f[i][j] = 1 + \min(f[i-1][j-1], f[i-1][j], f[i][j-1])\);
    • 否则, \(f[i][j] = 0\)。

实现代码如下:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 255;
int n, f[maxn][maxn];
char maze[maxn][maxn];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i ++) scanf("%s", maze[i]);
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            if (i == 0 || j == 0)
                f[i][j] = maze[i][j] == '1';
            else {
                if (maze[i][j] == '0')
                    f[i][j] = 0;
                else
                    f[i][j] = 1 + min(f[i-1][j-1], min(f[i][j-1], f[i-1][j]));
            }
        }
    }
    for (int k = 2; k <= n; k ++) {
        int cnt = 0;
        for (int i = k-1; i < n; i ++)
            for (int j = k-1; j < n; j ++)
                if (f[i][j] >= k)
                    cnt ++;
        if (cnt == 0) break;
        printf("%d %d\n", k, cnt);
    }
    return 0;
}
上一篇:栈与队列应用:迷宫问题(DFS非最短路径)


下一篇:[CodeForces][思维]NEKO's Maze Game