题目链接：uva 10593 - Kites

题目大意：给出一个n*n的图，表示一张纸板，问有多少种方法做成风筝，风筝必须是正方形或者是菱形，并且不能有洞。

解题思路：分正方形和菱形两种情况讨论：

• 正方形，dp[i][j]表示以i，j为右下角的正方形
  dp[i][j]=min(dp[i?1][j],dp[i][j?1])
  并且如果黄色部分也为'x'的话，dp[i][j]++
  
  

• 菱形，dp[i][j]表示菱形的正下角
  
  同样地市黄色部分如果为’x"的话，dp[i][j]++

  
  

  #include 
       
         #include 
        
          #include 
         
           using namespace std; const int N = 505; int n, dp[N][N]; char g[N][N]; int solve () { int ans = 0; memset(dp, 0, sizeof(dp)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (g[i][j] == 'x') { int tmp = min(dp[i-1][j], dp[i][j-1]); dp[i][j] = tmp + (g[i-tmp][j-tmp] == 'x'); if (dp[i][j] > 1) ans += dp[i][j] - 1; } } } memset(dp, 0, sizeof(dp)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (g[i][j] == 'x') { int tmp = min(dp[i-1][j-1], dp[i-1][j+1]); if (tmp == 0 || g[i-1][j] != 'x') dp[i][j] = 1; else if (g[i-tmp*2][j] == 'x' && g[i-tmp*2+1][j] == 'x') dp[i][j] = tmp + 1; else dp[i][j] = tmp; if (dp[i][j] > 1) ans += dp[i][j] - 1; } } } return ans; } int main () { while (scanf("%d%*c", &n) == 1 && n) { for (int i = 1; i <= n; i++) gets(g[i]+1); printf("%d\n", solve()); } return 0; }