問題描述：

小豬在小學中認識了很多的字，終于會寫一點作文了。某天小豬買了一張方格稿紙來寫作文，n 行 m 列。
某天小豬的鄰居小小豬來小豬家玩，用黑墨水筆把小豬新買的方格稿紙涂黑了很多格子。每個格子不是完全黑色就是完全白色。
小豬不能責怪小小豬。作文寫不成了，他覺得很無聊，就開始數里面有多少魔幻方陣。
如果稿紙中一個 k×k 的正方形區域滿足以下兩個條件，那么它就是魔幻方陣：
1．黑白格子的數量差不能超過1；
2．k不能小于2。
現在請你幫小豬求出他被染色的稿紙里面有多少個魔幻方陣。

輸入格式：

第一行有二個正整數 n 和 m（互相之間以一個空格分隔），表示稿紙共有 n行 m 列。
接下來 n 行，每行有 m 個 0 或 1 的整數（互相之間以一個空格分隔），代表每個格子的顏色。如果這個數是 1 則為黑色，是 0 則為白色。

輸出格式：

僅有一行，該行只有一個整數，表示稿紙中魔幻方陣的個數。

輸入樣例：

5 5
1 0 1 1 1
1 0 1 0 1
1 1 0 1 1
1 0 0 1 1
1 1 1 1 1

輸出樣例：

9
數據規模：
50%的數據，1≤n≤10，1≤m≤10；
75%的數據，1≤n≤180，1≤m≤180；
100%的數據，1≤n≤300，1≤m≤300。

---

解題思路：

數據不大，O(n^3)能過。
枚舉方陣邊長和左上角頂點即可。
求這個方陣中的黑色方格數，二維前綴和即可。

代碼：

#include<cmath> #include<cstdlib> #include<iostream> using namespace std; int n,m,a[301][301],q[301][301],s=0; int main() {freopen("paint.in","r",stdin);freopen("paint.out","w",stdout);cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>a[i][j];q[i][j]=q[i-1][j]+q[i][j-1]-q[i-1][j-1]+a[i][j];}for(int k=2;k<=n&&k<=m;k++)for(int i=1;i<=n-k+1;i++)for(int j=1;j<=m-k+1;j++){int x=i+k-1,y=j+k-1;int bl=q[x][y]-q[i-1][y]-q[x][j-1]+q[i-1][j-1];int wh=k*k-bl;if(abs(bl-wh)<=1)s++;}cout<<s;return 0; }

總結

以上是生活随笔為你收集整理的C++ 方格稿纸(paint)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。