【题解】【DP】基本DP实战：黑白棋盘判断

【题解】【DP】基本DP实战：黑白棋盘判断

题目来源：湖南大学程序设计训练2023：作业训练二 7 - 棋盘

【问题描述】

​ 棋盘是指一个行和列编号从1~N的NxN的二进制矩阵，当行号和列号之和为偶数时该矩阵对应位置为黑色的(1)，否则为白色的(0)。以下图示为N=1、2、3时的棋盘。

​ 給出一个NxN的二进制矩阵，请找出位于该矩阵内的最大尺寸的完整棋盘，以及最大尺寸棋盘的数量（棋盘可以交叠）。

【输入形式】

​ 每个测试用例的第一行是一个正整数N(1<=N<=2000)，表示給定矩阵的行数和列数，接下来的N行描述了这个矩阵：每行有N个字符，既可以是“1”（代表黑块），也可以是“0”（代表白块）。矩阵至少包含一个“1”字符。

【输出形式】

​ 输出最大尺寸棋盘的行列的大小，以及最大棋盘的个数，以空格分隔。

【样例输入】

5
00101
11010
00101
01010
11101

【样例输出】

3 3

DP 解题代码

// #pragma GCC optimize (2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int main() {
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<vector<int>> table(n + 1, vector<int>(n + 1, 0));
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= n; i++){
        string s;
        cin >> s;
        for (int j = 1; j <= n; j++)
            table[i][j] = s[j - 1] - '0';
    }
    int max_size = 0, max_num = 0;
    for (int i = 1, cell; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cell = table[i][j];
            // 以(i, j)为右下角的2x2格子符合棋盘要求，则进行状态转移
            if (table[i - 1][j - 1] == cell && 
                table[i - 1][j] != cell && 
                table[i][j - 1] != cell)
                /*
                    棋盘右下角一定为黑色。
                    以(i, j)为右下角的最大棋盘边长 = min(
                        以(i - 1, j - 1)为右下角的最大棋盘边长, 
                        以(i - 1, j)为右下角的最大棋盘边长, 
                        以(i, j - 1)为右下角的最大棋盘边长
                    ) + 1   ----->  "记得加上 1 以计入(i, j)本身"
                */
                dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
            // 若2x2格子不符合棋盘要求，则以(i, j)为右下角的最大棋盘边长为1，即(i, j)本身
            else
                dp[i][j] = 1;
            // 若(i, j)为白色，则并不是右下角为黑色的棋盘，故不计入max_size中
            if (cell == 0) continue;
            // 更新最大棋盘边长和最大棋盘数量
            if (dp[i][j] > max_size)
                max_size = dp[i][j], max_num = 1;
            else if (dp[i][j] == max_size)
                max_num++;
        }
    }
    cout << max_size << " " << max_num << endl;
    return 0;
}

时间复杂度：\(O(n^2)\)

空间复杂度：\(O(n^2)\)

常规解题方法：

// #pragma GCC optimize (2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char mat[205][205];
int maxSize = 1;
int maxNum = 0;
int n;
int rotate(int x, int y) {
/*
        扫描线：
        先：
        \
          \
            \
              \
                \
        后：
        ┘  │  │  │
        ───┘  │  │
        ──────┘  │
        ─────────┘
*/
    // 剪枝，先沿对角线检测最大棋盘
    int depth = 1;
    for(int a = x + 1, b = y + 1; a < n && b < n; a++, b++){
        if(mat[a][b] == '1') depth++;
        else break;
    };
    int floor = 1;
    for(; floor < depth; floor++){
        x++, y++;
        if(x == n || y == n) return floor;
        char symbol = '0';
        for(int i = 1; i <= floor; i++){
            if(mat[x - i][y] != symbol || mat[x][y - i] != symbol)
                return floor;
            symbol = (symbol == '1' ? '0' : '1');
        }
    }
    return depth;
}
int main() {
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> mat[i];
    int depth;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (mat[i][j] == '1') {
                depth = rotate(i, j);
                if(depth > maxSize) maxSize = depth, maxNum = 1;
                else if(depth == maxSize) maxNum++; 
            }
        }
    }
    cout << maxSize << " " << maxNum;
    return 0;
}

时间复杂度： \(\displaystyle \leq O(\sum_{i=1}^{n} \sum_{j=1}^{n} d_{ij}^2)\)，\(d_{ij}\) 指以 \((i,j)\) 为棋盘左上角的最大棋盘深度。无法直接求出，但远大于\(O(n^2)\)

空间复杂度：\(O(n^2)\)