$$農田個數$$

Description

你的老家在河北農村。過年時，你回老家去拜年。你家有一片N?M農田，將其看成一個N?M的方格矩陣，有些方格是一片水域。你的農村伯伯聽說你是學計算機的，給你出了一道題： 他問你：這片農田總共包含了多少個不存在水域的正方形農田。

兩個正方形農田不同必須至少包含下面的兩個條件中的一條：

邊長不相等

左上角的方格不是同一方格

Input

輸入數據第一行為兩個由空格分開的正整數N、M（1<=m 第2行到第N+1行每行有M個數字（0或1），描述了這一片農田。0表示這個方格為水域，否則為農田 $（注意：數字之間沒有空格，而且每行不會出現空格）$

Output

滿足條件的正方形農田個數。

Sample Input

3 3

110

110

000

Sample Output

5

題目大意：

一個n*n的板塊上有黑色（0）和白色（1）的正方形方塊，要求沒有黑色（0）的正方形有多少個

解題方法：

首先我們稱符合條件的正方形稱為A正方形（為了方便），這是一種規律：首先我們用f[i][j]來表示以(i,j)為右下角的A正方形邊長最大是多少，然后就蹦出了這個：

動態轉移方程：

$$f[i][j]=min(f[i?1][j?1],min(f[i?1][j],f[i][j?1]))+1$$

標注：

通過這個規律，我們求出了以（i,j）為右下角的A正方形邊長最大是多少，而且以這個方塊為右下角的A正方形的個數也是這個，這是因為這個是邊長最大的，邊長比它小的都存在各一個，所以加一加就是這個數，我們再把它們加在一起，就得出結果了

#include<cstdio> #include<iostream> using namespace std; int n,m,ans,f[1005][1005]; char x; int main() {scanf("%d%d",&n,&m);for (int i=1;i<=n;i++)for (int j=1;j<=m;j++){x=getchar();//因為沒有空格，所以要用字符輸入while (!((x>='0')&&(x<='9'))) x=getchar();//不為數字就再次輸入if (x==49) f[i][j]=min(f[i-1][j-1],min(f[i-1][j],f[i][j-1]))+1;//ASCLL碼中49為“1”，為1時就套用動態轉移方程ans+=f[i][j];//累加}printf("%d",ans);//輸出 }

總結

以上是生活随笔為你收集整理的【动态规划】农田个数 (ssl 1633)的全部內容，希望文章能夠幫你解決所遇到的問題。

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