我们对每一个点作为三角形的最上面顶点然后向下考虑，并且利用前缀和优化。
复杂度是n^3的。
但是我们如果知道上一个点的答案，那么之后的就可以少判断很多，相当于是记忆化，每一行最多访问一次。
AC代码：
#pragma GCC optimize("-Ofast","-funroll-all-loops") #include<bits/stdc++.h> //#define int long long using namespace std; const int N=2e3+10; int n,sum[N][N],res[N][N]; char g[N][N]; long long ans; signed main(){ cin>>n; for(int i=1;i<=n;i++) scanf("%s",g[i]+1); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) sum[i][j]=sum[i][j-1]+(g[i][j]=='#'); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(g[i][j]=='#'){ res[i][j]=max(1,res[i-1][j]-1); for(int k=i+res[i][j];k<=n;k++) if((j+(k-i))<=n&&(j-(k-i))>=1&&(k-i)*2+1==sum[k][j+(k-i)]-sum[k][j-(k-i)-1]) res[i][j]++; else break; ans+=res[i][j]; } cout<<ans; return 0; }