五彩斑斓（colorful）

题目描述

小 Z 最近收到了一个花花绿绿的矩阵，有 $n$ 行 $m$ 列，位置在第 $i$ 行第 $j$ 列的方格颜色是 $c_{ij}$。

小 Z 觉得一个矩阵是五彩斑斓的，当且仅当这个矩阵四个顶点上的颜色不都相同。

• 不都相同的意思是，当且仅当矩阵四个顶点上的 $c_{ij}$ 至少有一个和其他点颜色不同。

现在小 Z 想让你帮忙数一下，这个矩阵有多少个子矩阵是五彩斑斓的。

• 特殊的，原矩阵也算一种子矩阵，四个顶点都在同一个位置也算一种子矩阵。

输入格式

第一行两个正整数 $n,m$ ，代表矩阵的大小。

接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 个第 $j$ 个整数 $c_{ij}$ 代表这个位置的颜色。

输出格式

输出一个整数，代表五彩斑斓的子矩阵个数。

样例 #1

样例输入 #1

3 4
1 2 3 1
1 3 1 2
1 2 1 1

样例输出 #1

35

提示

对于 $20\%$ 的数据，$1\le n, m\le 80$。

对于另外 $20\%$ 的数据，$c_{i,j}=0$ 或 $1$。

对于 $80\%$ 的数据，$1\le c_{i,j}\le 400$。

对于全部数据，$1\le n,m\le 400, 0\le c_{i,j}\le 10^6$

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int> > matrix(n, vector<int>(m));
    for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) cin >> matrix[i][j];
    vector<vector<long long> > prefix(n + 1, vector<long long>(m + 1, 0));
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + (long long)matrix[i - 1][j - 1];
    long long colorful = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            for (int len1 = 1; i + len1 - 1 <= n; ++len1) {
                for (int len2 = 1; j + len2 - 1 <= m; ++len2) {
                    int color1 = matrix[i - 1][j - 1];
                    int color2 = matrix[i + len1 - 2][j - 1];
                    int color3 = matrix[i - 1][j + len2 - 2];
                    int color4 = matrix[i + len1 - 2][j + len2 - 2];
                    if (color1 != color2 || color1 != color3 || color1 != color4) colorful++;
                }
            }
        }
    }
    cout << colorful << endl;
    return 0;
}